链表问题总结 (上)

作者: 梦工厂 | 来源:发表于2015-09-10 12:44 被阅读1974次

【声明】
欢迎转载，但请保留文章原始出处→_→
文章来源：http://www.jianshu.com/p/08d085b34b2c
联系方式：zmhg871@gmail.com

【正文】
链表是非常基础和灵活的数据结构，在面试中出现的频率非常高。以下是我在学习《剑指offer》过程中对链表问题的总结，希望对大家复习有帮助。
（Java实现）

【目录】

单链表的创建和遍历
求单链表中节点的个数
查找单链表中的倒数第k个结点
查找单链表中的中间结点
合并两个有序的单链表，合并之后的链表依然有序
反转链表
从尾到头打印单链表
删除链表结点

【提示】
当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表，可以让其中一个指针遍历的速度快一些（比如一次在链表中走两步），或者让它先在链表上走几步。

求链表的倒数K个节点
求链表的中间节点
求链表中是否有环

单链表的创建和遍历：

public class LinkList {
 
     //Linked List Node
     static class LinkNode{
         int value;                // value for this node
         LinkNode next = null;     // Pointer to next node
 
         LinkNode(int data){
             value = data;
         }
 
         LinkNode(){}
     }
 
     private LinkNode header = null;
 
     //方法：向链表中添加数据
     public void add(int value){
         if(header == null) header = new LinkNode();
 
         LinkNode node = new LinkNode(value);
         node.next = header.next;
         header.next  = node;
     }
 
    //方法：遍历链表
     public void print(){
         if(header == null) return;
 
         LinkNode temp = header.next;
         while(temp != null){
             System.out.println("value : " + temp.value);
             temp = temp.next;
         }
     }
 
     public static void main(String[] args) {       
         LinkList list = new LinkList();
         //向LinkList中添加数据
         for (int i = 0; i < 7; i++) {
              list.add(i);
          }
 
         list.print();
         System.out.println(list.getSize());
      }
}

****求单链表中节点的个数：时间复杂度为O（n）****

//方法：获取单链表节点的个数
 public int getSize(){
     if(header == null) return 0;
     
     LinkNode temp = header.next;
     int size = 0;
     
     while(temp != null){
         size++;
         temp = temp.next;
     }
     
     return size;
 }

查找单链表中的倒数第k个结点

题目描述：输入一个单向链表，输出该链表中倒数第k个节点，链表的倒数第1个节点为链表的尾指针。（剑指offer，题15）

3.1 普通思路：（遍历链表2次）
首先计算出链表的长度size，然后输出第(size-k)个节点就可以了。
（注意链表为空，k为0，k大于链表中节点个数时的情况）。

public int getLastNode(int index){
     if(header == null || index == 0) return -1;
     
     int size = getSize();
     if(index > size) return -1;
     
     LinkNode temp = header.next;
     for(int i =1;i<= size-index;i++){
         temp = temp.next;
     }
     return temp.value;
 }

3.2 改进思路：（遍历链表1次）
声明两个指针：first和second，首先让first和second都指向第一个结点，然后让first结点往后挪k-1个位置，此时first和second就间隔了k-1个位置，然后整体向后移动这两个节点，直到first节点走到最后一个结点的时候，此时second节点所指向的位置就是倒数第k个节点的位置。

  public int getLastNode(int k){
     if(header == null || k<= 0) return -1;
     
     LinkNode first = header;
     LinkNode second = header;
     
     //让first结点往后挪k-1个位置
     for(int i =0;i<k-1;i++){
         if(first.next != null){
             first = first.next;
         }else{
             return -1;
         }
     }
     while(first.next != null){
         first = first.next;
         second = second.next;
     }
     return second.value;
}

查找单链表中的中间结点

题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。

4.1 普通思路：（遍历链表2次）
首先计算出链表的长度size，然后输出第(size/2)个节点就可以了。

     public int getMiddleNode(){
         if(header == null)
             return -1;
         
         //第1次遍历获取节点数
         LinkNode temp = header.next;
         int size = 0;
         while(temp != null){
             size++;
             temp = temp.next;
         }
         if(size == 0) return -1;
         
        //第2次遍历查找中间节点
         temp = header.next;
         for(int i=0;i<size/2;i++){
             temp = temp.next;
         }
         return temp.value;
     }

4.2 改进思路：（遍历链表1次）
声明两个指针：first和second，同时从链表头节点开始，一个指针每次移动两步，另一个每次移动一步，当走的快的指针走到链表的末尾时，走的慢的指针正好在链表的中间。

     public LinkNode getMiddleNode(){
         if(header == null)
             return null;
         
         LinkNode first = header; //快指针
         LinkNode second = header;
         
         while(first!=null && first.next!=null){
             first = first.next.next;
             second = second.next;
         }
         return second;
     }

合并两个有序的单链表，合并之后的链表依然有序

题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。（剑指offer，题17）
例如：
链表1： 1->3->5->7
链表2： 2->4->6->8
合并之后：1->2->3->4->5->6->7->8

解题思路 : 类似于归并排序
首先分析合并两个链表的过程。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点。
我们继续合并两个链表中剩余的结点。在两个链表中剩下的结点依然是排序的，因此合并这两个链表的步骤和前面的步骤是一样的。我们还是比较两个头结点的值。此时链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点的值将是合并剩余结点得到的链表的头结点。我们把这个结点和前面合并链表时得到的链表的尾节点链接起来。
当我们得到两个链表中值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的结点依然是排序的，因此合并的步骤和之前的步骤是一样的。这就是典型的递归的过程，我们可以定义递归函数完成这一合并过程。

 //两个参数代表的是两个链表的头结点,返回合并后的头结点
 public static LinkNode Merge(LinkNode head1,LinkNode head2){
     if(head1 == null) return head2;
     if(head2 == null) return head1;
     
     LinkNode mergeHead = null;
     if(head1.value <= head2.value){
         mergeHead = head1;
         mergeHead.next = Merge(head1.next,head2);
     }else{
         mergeHead = head2;
         mergeHead.next = Merge(head1,head2.next);
     }
     return mergeHead;
 }

注意问题：
1）链表不能断开，且仍为递增顺序；
2）代码鲁棒性，考虑链表为空的情况；

//遍历的方式
public static LinkNode Merge(LinkNode head1,LinkNode head2){
         
         //预判断
         if(head1 == null && head2 == null){
             return null;
         }
         if(head1 == null){
             return head2;
         }
         if(head2 == null){
             return head1;
         }
         
         LinkNode head;//新的头结点
         LinkNode temp;
         
         //确定新的头结点
         if(head1.value <= head2.value){
             head = head1;
             temp = head1;
             head1 = head1.next;
         }else{
             head = head2;
             temp = head2;
             head2 = head2.next;
         }
         //合并
         while(head1 != null && head2!=null){
             if(head1.value <= head2.value){
                 temp.next = head1;
                 temp = temp.next;
                 head1 = head1.next;
             }else{
                 temp.next = head2;
                 temp = temp.next;
                 head2 = head2.next;
             }
         }
         //合并剩余的元素
         if(head1 != null){
             temp.next = head1;
         }
         if(head2 != null){
             temp.next = head2;;
         }
         
         return head;
     }

查找单链表中的倒数第k个结点

题目描述：输入一个单链表的头结点，反转该链表并输出反转后的头结点。（剑指offer，题16）
例如：
链表反转前： 1->3->5->7
链表反转后： 7->5->3->1

解题思路 : 从头到尾遍历原链表，使用三个节点pNode、pPrev、pPost 记录当前节点，前一个节点和后一个节点。

public static LinkNode ReverseList(LinkNode header){
    if(header == null) return null;
    
    LinkNode pNode = header;
    LinkNode pPrev = null;   //记录前一个节点
    LinkNode pPost = null;   //记录后一个节点
    while(pNode != null){
        pPost = pNode.next;
        pNode.next = pPrev;
        pPrev = pNode;
        pNode = pPost;
    }
    return pPrev;
}

注意问题：链表为空和只有1个节点的问题。

****从尾到头打印单链表****

题目描述：输入一个链表的头结点，从尾到头反过来打印出每个节点的值. （剑指offer，题5）

7.1 解法1：在允许修改链表的结构的情况下，可以先反转链表，然后从头到尾输出。

7.2 解法2：在不允许修改链表的结构的情况下，可以使用栈实现。
遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的节点最后一个输出，而最后一个遍历到的节点第一个输出。这就是典型的“后入先出”，我们可以用栈来实现这种顺序。

 public static void reversePrint(LinkNode header){
     if(header == null) return;
     
     Stack<LinkNode> stack  = new Stack<>();
     LinkNode temp = header;
     
     while(temp!=null){
         stack.push(temp);
         temp = temp.next;
     }
     
     while(!stack.empty()){
         System.out.println(stack.pop().value);
     }
 }

7.3 解法3：在不允许修改链表的结构的情况下，可以使用递归实现。（递归的本质上就是一个栈结构）
要想实现反过来输出链表，每访问一个节点的时候，先递归输出它后面的节点，再输出节点自身，这样链表的输出结果就反过来了。

 public static void reversePrint(LinkNode header){
     if(header == null) return;
     
     reversePrint(header.next);
     System.out.println(header.value);
 }

代码简洁，但是链表非常长的情况下可能会导致函数调用栈溢出。所以显示使用栈基于循环实现的代码的鲁棒性会更好。

删除链表结点

题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。（剑指offer，题13）

8.1 普通思路：平均时间复杂度O(n)
从链表的头结点开始，顺序遍历要删除的节点，并在链表中删除该节点。

 public void delete(LinkNode head,LinkNode toBeDeleted){
     
     if(head == null || toBeDeleted == null)
         return;
     
     LinkNode prev = head;
     LinkNode temp = head.next;
     
     while( temp != null ){
         if(temp.value == toBeDeleted.value){
             prev.next = temp.next;
             break;
         }else{
             temp = temp.next;
             prev = prev.next;
         }
     }
     
 }

8.2 改进思路：平均时间复杂度O(1)
前一种方法之所以要从头开始查找，是因为我们需要得到被删除节点的前一个节点，但是想要删除节点并不一定非要找到前一个节点。由于在单链表中可以很方便的得到删除节点的下一个节点，如果我们把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除，就相当于把需要删除的节点删除了。

public class Test {
 /** 
  * 链表结点 
  */  
 public static class ListNode {  
     int value; // 保存链表的值  
     ListNode next; // 下一个结点  
 } 
 /** 
  * 【注意1：这个方法和文本上的不一样，书上的没有返回值，这个因为JAVA引用传递的原因， 
  *   如果删除的结点是头结点，如果不采用返回值的方式，那么头结点永远删除不了】 
  * 【注意2：输入的待删除结点必须是待链表中的结点，否则会引起错误，这个条件由用户进行保证】 
  * 
  * @param head        链表表的头 
  * @param toBeDeleted 待删除的结点 
  * @return 删除后的头结点 
  **/
 public static ListNode deleteNode(ListNode head,ListNode toBeDeleted){
     //预判断
     if(head == null)
         return null;
     if(toBeDeleted == null){
         return head;
     }
     // 如果删除的是头结点，直接返回头结点的下一个结点  
     if(head.value == toBeDeleted.value){
         return head.next;
     }
     // 在多个节点的情况下，如果删除的是最后一个元素  
     if(toBeDeleted.next == null){
         // 找待删除元素的前驱  
         ListNode temp = head;
         while(temp.next.value != toBeDeleted.value){
             temp = temp.next;
         }
         // 删除待结点  
         temp.next = null;
     }else{
         // 在多个节点的情况下，如果删除的是某个中间结点  
         toBeDeleted.value =  toBeDeleted.next.value;
         toBeDeleted.next  = toBeDeleted.next.next;
     }
    // 返回删除节点后的链表头结点  
     return head;
 }
 
 /** 
  * 输出链表的元素值 
  * 
  * @param head 链表的头结点 
  */  
 public static void printList(ListNode head) {  
     while (head != null) {  
         System.out.print("  value ：" + head.value);  
         head = head.next;  
     }  
     System.out.println();  
 } 
 
 public static void main(String[] args) {  
     ListNode head1 = new ListNode();  
     head1.value = 1;  
     ListNode head2 = new ListNode();  
     head2.value = 2;
     ListNode head3 = new ListNode();  
     head3.value = 3;  
     ListNode head4 = new ListNode();  
     head4.value = 4;  
    
     head1.next = head2;
     head2.next = head3;
     head3.next = head4;
     
     printList(head1);  
     ListNode head = head1;  
     // 删除头结点  
     head = deleteNode(head, head1);
     printList(head);  
     
     // 删除尾结点  
     head = deleteNode(head, head4);
     printList(head);  
     
     // 删除中间结点  
     head = deleteNode(head, head3);
     printList(head);  
     
     ListNode node = new ListNode();  
     node.value = 12;  
     // 删除的结点不在链表中  
     head = deleteNode(head, node);
     printList(head);  
 }  
}

考察思维创新能力，打破常规。当我们需要删除一个节点时，并不一定要删除这个节点本身，可以先把下一个节点的内容复制过来覆盖原来需要被删除节点的内容，然后把下一个节点删除。

参考资料：

[2015-9-10]

链表问题总结 (上)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

java收集

基本算法

链表

程序员

首页投稿（暂停使用，暂停投稿）

寒哥管理的技术专题

代码改变世界

Programming Hipster