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();
  }
}

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