链表知识点总结

65 阅读 0 评论 43 点赞

我是靠谱客的博主幽默身影，最近开发中收集的这篇文章主要介绍链表知识点总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

package 链表;

//定义一个结点
class Node{
   Node next = null;
   int data;
   public Node(int data){
       this.data = data;
   }
}

public class MyLinkedList {
   Node head = null;//链表的头结点

   //添加结点
   public void addNode(int data){
       //将数据封装到结点中，即创建新结点
       Node node = new Node(data);
       //如果链表是空链表，将新结点添加给头结点
       if(head == null){
           head = null;
           return;
       }
       //如果链表是非空链表，将新节点添加到链表末尾处
       Node tmp = head;
       while(tmp.next!=null){
           tmp = tmp.next;
       }

       tmp.next = node;
   }

   //删除结点
   public boolean delNode(int index){
       //角标不合理
       if(index<1 || index>length()){
           return false;
       }

       //特殊情况，index==1
       if(index == 1){
           head = head.next;
           return true;
       }
       //index大于等于2的情况
       int i =2;
       Node preNode = head;
       Node curNode = preNode.next;
       while(curNode!=null){
           if(index == i){
               preNode.next = curNode.next;
               return true;
           }
           preNode = curNode;
           curNode = curNode.next;
           i++;
       }
       return true;
   }

   /**
   * 对链表进行排序
   * 思路：用选择排序的思想对链表进行排序。第一个结点和第二个结点相比较，小的往前放；
   * 第一个结点和第三个结点相比较，小的往前放...第一次排序后，最小值放在第一个结点处。
   * 将第一个结点的下一个结点重新设为第一个结点，重复上述过程
   */
   public Node orderList(Node head){
       Node curNode = head;

       while(curNode.next!=null){
           Node nextNode = curNode.next;

           while(nextNode!=null){
               if(curNode.data>nextNode.data){
                   int tmp = curNode.data;
                   curNode.data = nextNode.data;
                   nextNode.data = tmp;
               }

               nextNode = nextNode.next;
           }

           curNode = curNode.next;
       }

       return head;
   }

   /**
   * 反转链表
   *
   * 思路：从头到尾遍历链表。在断开当前结点与下一个结点之间的联系之前，先将下一个
   * 结点保存，然后，让当前结点指向上一个结点，将当前结点定义为新的上一个结点，将
   * 当前结点的下一个结点定义为新的当前结点。直到当前结点的下一个结点为null，将
   * 当前结点定义为反转后的头结点。
   */
   public Node reverseList(Node head){
       if(head == null){
           return null;
       }

       Node currentNode = head;//定义当前结点，初始值为头结点
       Node preNode = null;//定义当前结点的上一个结点，初始值为null
       Node reverseHead = head;//定义反转后链表的头结点，初始值为head
       while(currentNode != null){
           Node aftNode = currentNode.next;//保存当前结点的下一个结点

           //如果当前结点为尾结点，当前结点即为反转后链表的头结点
           if(currentNode.next == null){
               reverseHead = currentNode;
           }
           currentNode.next = preNode;//断开当前结点与下一个结点的联系，并指向上一个结点
           preNode = currentNode;//将当前结点定义为新的上一个结点
           currentNode = aftNode;//将当前结点的下一个结点定义为新的当前结点
       }

       return reverseHead;
   }

   /**
   * 求链表中倒数第k个结点
   *
   * 思路：在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k-1步，然后
   * 两个指针同时往前移动。循环直到先行指针指向尾结点时，另一个指针所指的位置就是所
   * 要找的位置。
   *
   * @param head
   * @param k
   * @return
   */
   public Node findElem(Node head,int k){
       //判断k是否合理
       if(k<1 && k>length()){
           return null;
       }

       //定义两个指针，p1和p2
       Node p1 = head;
       Node p2 = head;

       //让p1指针先前移k-1步
       for(int i=0;i<k-1&&p1!=null;i++)
           p1 = p1.next;

       if(p1 == null){
           System.out.println("k不合法");
           return null;
       }

       //两个指针同时向前移动，当先行指针指向尾结点时，另一个指针所指的位置就是所要找的位置
       while(p1.next != null){
           p1 = p1.next;
           p2 = p2.next;
       }

       return p2;
   }

   /**
   * 如何判断两个链表是否相交
   *
   * 思路：如果两个链表相交，那么它们一定有着相同的尾结点，因此实现思路为，分别遍历
   * 两个链表，记录它们的尾结点，如果它们的尾结点相同，那么说明这两个链表相交，否则
   * 不相交。
   *
   * @param head1
   * @param head2
   * @return
   */
   public boolean isIntersect(Node head1,Node head2){
       if(head1==null || head2==null){
           return false;
       }

       //找出第一个链表的尾结点
       Node tail1 = head1;
       while(tail1.next != null){
           tail1 = tail1.next;
       }
       //找出第二个链表的尾结点
       Node tail2 = head2;
       while(tail2.next != null){
           tail2 = tail2.next;
       }

       return tail1 == tail2;
   }

   /**
   * 如何检测一个单链表是否有环
   *
   * 思路：定义两个指针fast和slow，快指针一次走两步，慢指针一次走一步，快指针每移动
   * 一次都要根慢指针比较，直到当快指针等于慢指针时，说明这个链表是带环的单向链表，否则
   * 说明这个链表不是带环的单向链表。
   *
   * @param head
   * @return
   */
   public boolean hasCycle(Node head){
       if(head == null){
           return false;
       }

       Node fast = head;
       Node slow = head;
       while(fast!=null&&fast.next!=null){
           slow = slow.next;
           fast = fast.next.next;
           if(slow == fast){
               return true;
           }
       }
       return false;
   }

   //计算链表长度
   public int length(){
       Node tmp = head;
       int length = 0;
       while(tmp!=null){
           length++;
           tmp = tmp.next;
       }
       return length;
   }

   //打印链表
   public void printList(){
       Node tmp = head;
       while(tmp!=null){
           System.out.println(tmp.data);
           tmp = tmp.next;
       }
   }
}