天天看點
傳回

算法問題總結-連結清單相關删除連結清單結點查找特定節點環與相交改變連結清單順序其它操作參考

作者：YouChuang

本文主要是對劍指offer及平時遇到的連結清單相關的題目做了部分總結

  • 删除連結清單結點
    • O1時間内删除連結清單指定結點
    • 删除重複結點
  • 查找特定節點
    • 倒數第k個結點
    • 查找中間結點
  • 環與相交
    • 判斷是否存在環
    • 查找環的入口
    • 兩個連結清單是否相交
    • 相交的第一個結點
  • 改變連結清單順序
    • 反轉連結清單
  • 其它操作
    • 複制複雜連結清單
  • 參考

删除連結清單結點

O(1)時間内删除連結清單指定結點

給定指定連結清單的頭結點和目标結點，在O(1)的時間内删除掉該目标結點

  • 思路

    一般思路：

    從頭結點周遊連結清單，找到指定結點然後删除，但是這樣會帶來O(n)的時間開銷，不滿足題意。存在的問題是查找都是從頭結點開始，時間過長。

    優化思路：

    抽象認識問題，删除結點其實本質上就是删除該結點中存放的資料，另外删除結點的本質方法就是找到該結點的前一個結點然後實施删除。

    基于這兩種認識，提出将目前結點的下一個結點作為目标結點，将兩者的資料交換，就可以得到前一個結點（即之前的目标結點）

  • 邊界條件

    針對目标結點為尾結點的情況，我們無法找到下一個結點來删除，是以就采用傳統的方法來進行删除，總體的時間複雜度為((n-1) * 1 + n * 1) / n，還是O(1)的複雜度

删除重複結點

在一個排序的連結清單中，存在重複的結點，請删除該連結清單中重複的結點，重複的結點不保留，傳回連結清單頭指針。 例如，連結清單1->2->3->3->4->4->5 處理後為 1->2->5

  • 思路

    特别注意，不是隻删除掉重複的結點，而是隻要該結點出現重複，則所有相關結點都删掉（包括源結點）

  • 邊界條件

    連結清單為空或隻有一個結點

    所有結點都為重複（重複同一個資料或者多種重複資料）

    包括頭結點在内的前幾個結點發生重複

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
  ListNode deleteDuplication(ListNode pHead)
  {
        /*
        work、pre雙指針
        */
        if(pHead == null)
            return pHead;

        //用來标記是否出現重複結點
        int tag = ;
        ListNode ppre, pwork, pnext;
        ppre = null;
        pwork = pHead;
        pnext = pwork.next;

        while(pnext != null)
        {
            if(pwork.val == pnext.val)
            {
                tag = ;
                pwork.next = pnext.next;
                pnext.next = null;
                pnext = pwork.next;
            }
            else
            {
                if(tag == )
                {
                    //說明之前出現了重複結點，如果是在頭結點就出現這種情況需要小心處理
                   if(pwork == pHead)
                    {
                        pwork = pnext;
                        pnext = pnext.next;
                        pHead = pwork;
                    }
                    else
                    {
                        ppre.next = pnext;
                        pwork = pnext;
                        pnext = pnext.next;                        
                    }
                tag = ;
                }
                else
                {                
                    ppre = pwork;
                    pwork = pnext;
                    pnext = pnext.next;
              }
            }
        }

        //如果最後部分全部重複，整個連結清單都是重複資料，則全部删除處理
        if(tag == )
        {
            if(pHead == pwork)
            {
                pHead = pnext;            
            }
            else
            {
                ppre.next = pnext;
                pwork.next = null;
            }
        }
        return pHead;
  }
}

查找特定節點

倒數第k個結點

輸入一個連結清單，輸出該連結清單中倒數第k個結點。

  • 思路

    正常思路，兩個工作指針，一前一後出發

  • 邊界條件

    計數k與結點為null兩個條件的控制

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
  public ListNode FindKthToTail(ListNode head,int k) {

        if((head == null) || (k == ))
            return null;

        /* 前者先走的步數 */
        int num = k; 
        ListNode ppre;
        ListNode pwork;
        ppre = pwork = head;

        /* pwork先走k步 */
        while((num > ) && (pwork != null)){
            pwork = pwork.next;
            num--;
        }

        /* k若超過了連結清單的範圍 */
        if(pwork == null){
           return null;
        }

        /* 同時後移 */ 
        while(pwork.next != null){
            pwork = pwork.next;
            ppre = ppre.next;
        }
        return ppre;

    }
}

查找中間結點

思路：跟上面的類似，隻不過兩個工作指針同時出發，步幅不同

環與相交

判斷是否存在環

思路：

若是連結清單存在環的話，則兩個速度不同的工作指針，肯定會在環中相遇。

設定兩個工作指針，同時出發，步幅不同，兩者相遇則證明有環，否則會周遊結束

具體的實作在下面問題中有代碼

查找環的入口

一個連結清單中包含環，請找出該連結清單的環的入口結點。

  • 思路

    經典問題，相關問題還有幾個，稍後補上，再總結一下

    需要數學推導，簡單說下過程：

    假設非環連結清單長度為K（長度即為結點個數，非環連結清單不包含環的入口結點），環的長度為L，兩個工作指針ppre、pnext，ppre的速度為spre，pnext的速度為snext；

    假設兩個指針同時從頭結點（不計入長度之内）出發，向前走了x次，即ppre走了spre*x步，pnext走了spnext*x步，則兩者在環中相交時（這裡有兩個問題，判斷連結清單是否有環以及預設兩個結點是在環中的第一圈即相遇，稍後解決）

    (ppre*x - K) % L = (pnext*x - K) % L

    ((pnext - ppre) * X) % L = 0

    假設pnext的速度為2，ppre為1

    則X % L = 0，即X = L

    則兩者相交的地方在X-K=L-K的地方，即環中距離環入口處L-K個位置的地方

    這時可以看出相交處再次到達環入口的距離為K，與連結清單頭結點到環入口的距離相同

    稍後補上圖檔來做說明，可能會更好了解一下

    則本題目的思路也就出來了

    先讓兩個指針ppre、pnext分别以1、2的速度同時周遊連結清單，知道兩者相遇

    然後ppre指針重回頭結點，pnext不變，接着ppre和pnext同時以速度1繼續周遊，直到再次相遇，則相遇的地方即為環的入口結點

以下圖為例

K為3，L為7，則X=L=7，即ppre指針向前走了7步，pnext向前走了14步，兩者第一次相聚在X-K=4，距離入口4步的位置，然後再繼續前行3步即可再次達到環的入口處

算法問題總結-連結清單相關删除連結清單結點查找特定節點環與相交改變連結清單順序其它操作參考

  • 邊界條件

    連結清單本身即為環

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    ListNode EntryNodeOfLoop(ListNode pHead)
    {

        if(pHead == null || pHead.next == null)
            return null;

        ListNode pwork = pHead;
        ListNode pa, pb;
        pa = pb = pHead;

        /** 找到兩個結點在環中相遇的結點 */
        while(pa != null && pa.next != null)
        {
            pa = pa.next;
            pb = pb.next.next;

            if(pa == pb)
            {
                //若是相遇，則跳出循環繼續處理
                break;
            }
        }

        //若兩者在環的入口處相遇，則連結清單本身為環
        if(pa == pHead)
            return pa;

        if(pa != null)
        {
          pa = pHead;
            while(pa != null && pa.next != null)
            {
                pa = pa.next;
                pb = pb.next;

               if(pa == pb)
               {
                  //若是相遇，則跳出循環繼續處理
                  return pa;
              }
            }
        }
        return pa;
    }
}

兩個連結清單是否相交

兩個單連結清單，判斷是否相交

  • 思路

    首先明确一點，若是兩個連結清單相交，則兩個連結清單的尾結點必定相同，頭結點不同

    最基本思路，對連結清單1中的每一個結點周遊連結清單2

    優化思路一，轉化成環的問題，将連結清單2的頭部接在連結清單1後面，若是兩個連結清單相交，則連結清單2變成環，直接判斷連結清單2是否為滿環即可（周遊一遍是否回到起點）

    優化思路二，因為兩個相交連結清單的尾結點必定相同，則直接分别找到兩個連結清單的尾結點，然後比較即可

如果連結清單中可能有環，判斷是否相交

  • 思路

    若是有環的連結清單相交，由于相交連結清單尾結點必定相同，則兩個連結清單的環必定重合

    那麼就可以直接判斷連結清單一中環的入口結點是否在另一個連結清單上出現即可。

相交的第一個結點

兩個單連結清單

  • 思路

    基于優化思路一，則找到新的帶環連結清單的環入口結點即為相交的第一個結點

    基于優化思路二，則需先确定兩個連結清單長度，然後基于短連結清單，周遊長連結清單結點到相同的位置，然後兩個連結清單同時周遊并比較結點是否相同，直至末尾，代碼見下方

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {   
        /** 
         * 邊界條件處理，其中一個連結清單為空或者隻有一個結點則不成立，兩個連結清單頭部不能重合，不然就完全重合
         * 連結清單1的末尾指針、工作指針，連結清單2的末尾、工作指針
         */
        ListNode pwork1, pwork2, pwork;
        pwork1 = pHead1;
        pwork2 = pHead2;

        int len1 = , len2 = , tmp = ;

        /** 擷取連結清單長度，比較，然後周遊對齊 */
        while(pwork1 != null){
            len1++;
            pwork1 = pwork1.next;
        }
        while(pwork2 != null){
            len2++;
            pwork2 = pwork2.next;
        }
        pwork1 = pHead1;
        pwork2 = pHead2;
        tmp = len1 - len2;
        if(tmp > ){
            while(tmp > ){
                pwork1 = pwork1.next;
                tmp--;
            }
        }else if(tmp < ){
            while(tmp < ){
                pwork2 = pwork2.next;
                tmp++;
            }
        }

        /** 開始周遊并判斷 */
        while((pwork1 != pwork2) && (pwork1 != null)){
            pwork1 = pwork1.next;
            pwork2 = pwork2.next;
        }

        return pwork1;

    }

}

改變連結清單順序

反轉連結清單

輸入一個連結清單，反轉連結清單後，輸出反轉連結清單後頭節點

  • 思路

    非遞歸思路：比較簡單的思路，三個工作指針

    遞歸思路：注意如何結束遞歸

  • 邊界條件

    注意不要讓null指針再取next

非遞歸方式 
/*public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {

        if((head == null) || (head.next == null))
            return head;
        ListNode ppre = null;
        ListNode pwork = null;
        ListNode pnext = null;
        pwork = head;
        //pnext = head.next;
        while(pwork != null){
            /* 
            如果按照下面這樣編碼的話，則會出現一種情況就是pwork不為null，pnext已經為null，然後最後一句再對pnext取next則會出錯。
            pnext = head.next;
          while(pwork != null){
              pwork.next = ppre;
              ppre = pwork;
              pwork = pnext;
              pnext = pnext.next;
           }
            */
            pnext = pwork.next;
            pwork.next = ppre;
            ppre = pwork;
            pwork = pnext;

        }
        //head = ppre;
        return ppre;

    }
}
遞歸方式 
public class Solution {
    public ListNode ReverseList(ListNode head) {
        /** 遞歸結束條件 */
        if((head == null) || (head.next == null))
            return head;

        /** 逆置兩個結點 */
        ListNode pNewHead = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return pNewHead;
    }
}

其它操作

複制複雜連結清單

複制複雜連結清單，連結清單有next指針和random指針，random指向任意結點

  • 思路

    普通思路：

    先複制next指針的連結清單，再逐個結點周遊random指針，并對找到的對應結點重新周遊連結清單記錄其所在位置，最後更改新連結清單對應結點的random指針。存在的問題，random結點的定位比較難

    巧妙思路：

    将新連結清單和舊連結清單的結點之間建立一個映射關系，當周遊random時，将原結點和對應的random結點分别映射到新連結清單的對應結點中即可。存在的問題，需要專門的存儲空間來存放映射關系

    更為巧妙的思路：

    将映射關系與直接用連結清單的next指針來存儲，一個指針多用，舊連結清單的結點與新連結清單的結點的映射關系就是next關系。建立完畢後，建立相應的random指針關系，最後再拆分為新舊連結清單。

  • 邊界條件 
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/

public class Solution {
  public RandomListNode Clone(RandomListNode pHead)
  {       
        /** 邊界條件判斷 */
        if(pHead == null){
            return null;
        }
        RandomListNode pHeadWork = null;
        pHeadWork = pHead;
        /**
         * 先原地複制next指針連結清單，建立新舊連結清單的同時建立映射關系
         */
        while(pHeadWork != null){
            RandomListNode pNewNode = new RandomListNode(pHeadWork.label);
            //pNewNode.label = pHeadWork.label;
            pNewNode.random = null;
            pNewNode.next = pHeadWork.next;
            pHeadWork.next = pNewNode;
            pHeadWork = pNewNode.next;
        }

        /**
         * 基于映射關系，建立random連結清單關系
         */
        pHeadWork = pHead;
        while(pHeadWork != null){
            if(pHeadWork.random != null){
                pHeadWork.next.random = pHeadWork.random.next;
            }
            pHeadWork = pHeadWork.next.next;
        }

        /**
         * 解開連結清單成兩個連結清單
         */
        RandomListNode pNewHead = null, pNewHeadWork = null;
        pNewHead = pHead.next;
        pNewHeadWork = pNewHead;
        pHeadWork = pHead;
        pHeadWork.next = pHeadWork.next.next;
        pHeadWork = pHeadWork.next;
        while(pHeadWork != null){
            pNewHeadWork.next = pHeadWork.next;
            pNewHeadWork = pNewHeadWork.next;
            pHeadWork.next = pHeadWork.next.next;
            pHeadWork = pHeadWork.next;

        }
        return pNewHead;

    }
}

參考

http://wuchong.me/blog/2014/03/25/interview-link-questions/

http://blog.csdn.net/heyabo/article/details/7610732

http://blog.csdn.net/liuhuiyi/article/details/8742571

資料結構與算法 連結清單 劍指offer
上一篇: 連結清單相關算法
下一篇: 算法基礎06-連結清單相關面試題總結1 連結清單問題

繼續閱讀