Java实现单链表的各种操作

主要内容:

  • 单链表的基本操作
  • 删除重复数据
  • 找到倒数第k个元素
  • 实现链表的反转
  • 从尾到头输出链表
  • 找到中间节点
  • 检测链表是否有环
  • 在不知道头指针的情况下删除指定节点
  • 如何判断两个链表是否相交并找出相交节点

直接上代码,就是这么奔放~~~

package pers.ty.$1101datastructure;
import java.util.Hashtable;
/**
 * @author Administrator
 * 实现单链表的基本操作,增加删除节点、排序、打印、计算长度
 */
public class MyLinkedList {
  Node head = null;//链表头的作用
  /**向链表中插入数据
   * @param d:插入数据的内容
   */
  public void addNode(int d){
    Node newNode=new Node(d);
    if(head==null){
      head=newNode;
      return;
    }
    Node tmp=head;
    while(tmp.next!=null){
      tmp=tmp.next;
    }
    //add Node to end
    tmp.next=newNode;
  }
  /**
   * @param index:删除第index个节点
   * @return 成功返回true,失败返回false
   */
  public Boolean deleteNode(int index){
    if(index<1||index>length()){
      return false;//删除元素位置不合理
    }
    //删除链表中的第一个元素
    if(index==1){
      head=head.next;
      return true;
    }
    int i=1;
    Node preNode=head;
    Node curNode=preNode.next;
    while(curNode!=null){
      if(i==index){
        preNode.next=curNode.next;
        return true;
      }
      preNode=curNode;
      curNode=curNode.next;
      i++;
    }
    return true;
  }
  /**
   * @return 返回链表的长度length
   */
  public int length(){
    int length=0;
    Node tmp=head;
    while(tmp!=null){
      length++;
      tmp=tmp.next;
    }
    return length;
  }
  /**
   * 对链表进行排序
   * @return 返回排序后的头结点
   */
  public Node orderList(){
    Node nextNode=null;
    int temp=0;
    Node curNode=head;
    while(curNode.next!=null){
      nextNode=curNode.next;
      while(nextNode!=null){
        if(curNode.data>nextNode.data){
          temp=curNode.data;
          curNode.data=nextNode.data;
          nextNode.data=temp;
        }
        nextNode=nextNode.next;
      }
      curNode=curNode.next;
    }
    return head;
  }
  /**
   * 打印链表中所有数据
   */
  public void printList(){
    Node tmp=head;
    while(tmp!=null){
      System.out.print(tmp.data+" ");
      tmp=tmp.next;
    }
    System.out.println();
  }
  /**
   * 从链表中删除数据的第一种方法
   * 遍历链表,把遍历到的数据存到一个Hashtable中,在遍历过程中若当前访问的值在Hashtable
   * 中存在,则可以删除
   * 优点:时间复杂度低  缺点:需要额外的存储空间来保存已访问过得数据
   */
  public void deleteDuplecate1(){
    Hashtable<Integer,Integer> table=new Hashtable<Integer,Integer>();
    Node tmp=head;
    Node pre=null;
    while (tmp!=null) {
      if(table.containsKey(tmp.data))
        pre.next=tmp.next;
      else{
        table.put(tmp.data, 1);
        pre=tmp;
      }
      tmp=tmp.next;
    }
  }
  /**
   * 从链表中删除重复数据的第二种方法
   * 双重循环遍历
   * 优缺点很明显
   */
  public void deleteDuplecate2(){
    Node p=head;
    while (p!=null) {
      Node q=p;
      while(q.next!=null){
        if(p.data==q.next.data){
          q.next=q.next.next;
        }else{
          q=q.next;
        }
      }
      p=p.next;
    }
  }
  /**
   * @param k:找到链表中倒数第k个节点
   * @return 该节点
   * 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点
   */
  public Node findElem(Node head,int k){
    if(k<1||k>this.length())
      return null;
    Node p1=head;
    Node p2=head;
    for (int i = 0; i < k-1; i++)
      p2=p2.next;
    while (p2.next!=null) {
      p2=p2.next;
      p1=p1.next;
    }
    return p1;
  }
  /**
   * 实现链表的反转
   * @param head链表的头节点
   */
  public void reverseIteratively(Node head){
    Node pReversedHead=head;
    Node pNode=head;
    Node pPrev=null;
    while (pNode!=null) {
      Node pNext=pNode.next;
      if(pNext==null)
        pReversedHead=pNode;
      pNode.next=pPrev;
      pPrev=pNode;
      pNode=pNext;
    }
    this.head=pReversedHead;
  }
  /**
   * 通过递归从尾到头输出单链表
   * @param head
   */
  public void printListReversely(Node head){
    if(head!=null){
      printListReversely(head.next);
      System.out.print(head.data+" ");
    }
  }
  /**
   * 查询单链表的中间节点
   * 定义两个指针,一个每次走一步,一个每次走两步...
   * @param head
   * @return q为中间节点
   */
  public Node searchMid(Node head){
    Node q=head;
    Node p=head;
    while (p!=null&&p.next!=null&&p.next.next!=null) {
      q=q.next;
      p=p.next.next;
    }
    return q;
  }
  /**
   * 在不知道头指针的情况下删除指定节点
   * 链表尾节点无法删除,因为删除后无法使其前驱节点的next指针置为空
   * 其他节点,可以通过交换这个节点与其后继节点的值,然后删除后继节点
   * @param n
   * @return
   */
  public boolean deleteNode(Node n){
    if(n==null||n.next==null)
      return false;
    int tmp=n.data;
    n.data=n.next.data;
    n.next.data=tmp;
    n.next=n.next.next;
    return true;
  }
  /**
   * 判断两个链表是否相交
   * 如果两个链表相交,则肯定有相同的尾节点,遍历两个链表,记录尾节点,看是否相同
   * @param h1链表1的头节点
   * @param h2链表2的头结点
   * @return 是否相交
   */
  public boolean isIntersect(Node h1,Node h2){
    if(h1==null||h2==null)
      return false;
    Node tail1=h1;
    while (tail1.next!=null){
      tail1=tail1.next;
    }
    Node tail2=h2;
    while(tail2.next!=null){
      tail2=tail2.next;
    }
    return tail1==tail2;
  }
  /**
   * 找出相交的第一个节点
   * @param h1
   * @param h2
   * @return
   */
  public Node getFirstMeetNode(Node h1,Node h2){
    if(h1==null||h2==null)
      return null;
    Node tail1=h1;
    int len1=1;
    while (tail1.next!=null){
      tail1=tail1.next;
      len1++;
    }
    Node tail2=h2;
    int len2=1;
    while(tail2.next!=null){
      tail2=tail2.next;
      len2++;
    }
    if(tail1!=tail2){
      return null;
    }
    Node t1=h1;
    Node t2=h2;
    //找出较长的链表先遍历
    if(len1>len2){
      int d=len1-len2;
      while(d!=0){
        t1=t1.next;
        d--;
      }
    }
    if(len1<len2){
      int d=len2-len1;
      while(d!=0){
        t2=t2.next;
        d--;
      }
    }
    while(t1!=t2){
      t1=t1.next;
      t2=t2.next;
    }
    return t1;
  }
  public static void main(String[] args) {
    MyLinkedList list=new MyLinkedList();
  }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持我们!

(0)

相关推荐

  • Java 数据结构链表操作实现代码

    链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表.循环链表.双向链表,下面将逐一介绍.链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一.链表的简介 二.链表实现原理和必要性 三.单链表示例 四.双链表示例 一.链表的简介 链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析.链表中数据就像被一个链

  • Java模拟有序链表数据结构的示例

    有序链表: 按关键值排序.删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置. 插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1), 如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择 优先级队列 可以使用有序链表来实现 有序链表的插入排序: 对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2) 复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,

  • Java单链表基本操作的实现

    最近被问到链表,是一个朋友和我讨论Java的时候说的.说实话,我学习编程的近一年时间里,学到的东西还是挺少的.语言是学了Java和C#,关于Web的学了一点Html+css+javascript.因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究.但链表这个东西我还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧. 但是我还是抽了一个晚上加半天的时间看了一下单向链表.并且使用Java试着写了一个实例出来.没有接触过链表的朋友可以作为参考,希望大家多提宝贵

  • JAVA实现链表面试题

    这份笔记整理了整整一个星期,每一行代码都是自己默写完成,并测试运行成功,同时也回顾了一下<剑指offer>这本书中和链表有关的讲解,希望对笔试和面试有所帮助. 本文包含链表的以下内容: 1.单链表的创建和遍历 2.求单链表中节点的个数 3.查找单链表中的倒数第k个结点(剑指offer,题15) 4.查找单链表中的中间结点 5.合并两个有序的单链表,合并之后的链表依然有序[出现频率高](剑指offer,题17) 6.单链表的反转[出现频率最高](剑指offer,题16) 7.从尾到头打印单链表(

  • Java单链表的实现代码

    下面是小编给大家分享的一个使用java写单链表,有问题欢迎给我留言哦. 首先定义一个Node类 public class Node { protected Node next; //指针域 public int data;//数据域 public Node( int data) { this. data = data; } //显示此节点 public void display() { System. out.print( data + " "); } } 接下来定义一个单链表,并实现

  • Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1.集合中必存在唯一的一个"第一元素": 2.集合中必存在唯一的一个 "最后元素" : 3.除最后一个元素之外,均有 唯一的后继(后件):

  • java实现单链表、双向链表

    本文实例为大家分享了java实现单链表.双向链表的相关代码,供大家参考,具体内容如下 java实现单链表: package code; class Node { Node next; int data; public Node(int data) { this.data=data; } } class LinkList { Node first; //头部 public LinkList() { this.first=null; } public void addNode(Node no) {

  • JAVA 数据结构链表操作循环链表

    JAVA 链表操作:循环链表 主要分析示例: 一.单链表循环链表 二.双链表循环链表 其中单链表节点和双链表节点类和接口ICommOperate<T>与上篇一致,这里不在赘述.参考:JAVA链表操作:单链表和双链表http://www.jb51.net/article/95113.htm 一.单链表循环链表 package LinkListTest; import java.util.HashMap; import java.util.Map; public class SingleCycle

  • Java实现双向链表(两个版本)

    临近春节,项目都结束了,都等着回家过年了.下面是小编给大家研究数据结构的相关知识,链表算是经常用到的一种数据结构了,现将自己的实现展示如下,欢迎大神赐教. 第一个版本,没有最后一个节点,每次从根节点开始遍历 public class LinkedList<E> { private Node head; public LinkedList() { } public E getFirst(){ if(head==null){ return null; } return head.value; }

  • java 数据结构之删除链表中的元素实例代码

    java 删除链表中的元素 以下实例演示了使用 Clear() 方法来删除链表中的元素: import java.util.*; public class Main { public static void main(String[] args) { LinkedList<String> lList = new LinkedList<String>(); lList.add("1"); lList.add("8"); lList.add(&q

随机推荐