連結清單問題彙總

1 前言
2 題目
- 2.1 連結清單中倒數第k個結點
- - 2.1.1 題目
  - 2.1.2 思路
  - 2.1.3 代碼
- 2.2 反轉連結清單
- - 2.2.1 題目
  - 2.2.2 思路
  - 2.2.3 代碼
- 2.3 合并兩個排序的連結清單
- - 2.3.1 題目
  - 2.3.2 思路1
  - 2.3.3 代碼1
  - 2.3.4 思路2
  - 2.3.5 代碼2
- 2.4 兩個連結清單的第一個公共結點
- - 2.4.1 題目
  - 2.4.2 思路
  - 2.4.3 代碼
  - 2.4.4 圖解
- 2.5 複雜連結清單的複制
- - 2.5.1 題目
  - 2.5.2 思路
  - 2.5.3 圖解
  - 2.5.4 代碼
- 2.6 連結清單中環的入口結點
- - 2.6.1 題目
  - 2.6.2 思路
  - 2.6.3 圖解
  - 2.6.4 代碼
- 2.7 删除連結清單中重複的結點
- - 2.7.1 題目
  - 2.7.2 思路1
  - 2.7.3 代碼1
  - 2.7.4 思路2
  - 2.7.5 代碼2
參考

1 前言

整理下劍指offer連結清單問題。

2 題目

2.1 連結清單中倒數第k個結點

2.1.1 題目

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

2.1.2 思路

思路：

如果輸對外連結表正向的第k個結點會嗎？應該會的！那麼再得到長度，一減，就ok了啊！
但是上面思路太麻煩，有一個非常牛逼的思路！
牛逼思路：我們可以定義兩個指針。
- 第一個指針從連結清單的頭指針開始周遊向前走k-1，第二個指針保持不動；
- 從第k步開始，第二個指針也開始從連結清單的頭指針開始周遊。
- 由于兩個指針的距離保持在k-1，當第一個（走在前面的）指針到達連結清單的尾結點時，第二個指針（走在後面的）指針正好是倒數第k個結點。
圖示：

劍指offer | 連結清單問題彙總1 前言2 題目參考

2.1.3 代碼

代碼寫起來！
寫代碼發現有報錯，考慮下邊界條件：如果查詢的是最後一個元素咋辦？也就是倒數第一個！

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        fast = slow = head
        '''
        為什麼這種思路ok？
		因為是循環k次，也就是距離為k 這時候就不能以.next作為循環終止條件了！而是自己為終止條件！但還是下面一種好思考一些！
        '''
        for _ in range(k):
            if not fast: # 如果fast為空 傳回空 
                return None
            fast = fast.next
        while fast:
            slow, fast = slow.next, fast.next
        return slow

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        # 邊界條件！
        if head == None or k == 0:
            return None
        # 初始化指針
        phead = head
        pbehind = head
        # 先走k-1步
        for i in range(k-1):
            if phead.next == None: # 防止出現連結清單就1個元素 然後說倒數第二個元素 這樣就gg
                return None
            else:
                phead = phead.next
        while phead.next != None: # 隻要走在前面的指針的下一步不是指向None 那麼就繼續移動！
            phead = phead.next
            pbehind = pbehind.next
        return pbehind

注意return的結果！！！不要把元素搞出來！看題目的需求！！！是傳回節點！！！現在直接傳回節點就ok！是以審題相當重要！

2.2 反轉連結清單

2.2.1 題目

輸入一個連結清單，反轉連結清單後，輸出新連結清單的表頭。

2.2.2 思路

思路：

如何反轉呢？也就是把元素全部倒置過來！如何實作？
能不能依次存儲到一個list 然後反轉list？好像不太行吧？因為最後要輸出表頭诶？就是直接輸出一個節點！
我好像隻要找到新連結清單的表頭就ok了？是以不需要存儲？那直接周遊到最後一個輸出？不行的！輸出就是反轉的連結清單！

劍指offer | 連結清單問題彙總1 前言2 題目參考

代碼思路：

每一步解釋下面都有！
值得注意的就是最後傳回的是pre！
一開始pre的定義是None！因為首節點反轉之後要指向None！巧妙！
循環體部分包括兩部分：
- 轉換節點方向【先儲存下一個指向資訊再轉向】
- 移動指針【直接前一個指向後一個後一個指向之前儲存的next！】
注意考慮特殊情況
- 空連結清單
- 隻有1個節點的連結清單的情形！

2.2.3 代碼

代碼：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 傳回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None:
            return None
        # 定義兩個指針
        pre = None #前一個節點 因為頭節點反轉後需要指向None
        cur = pHead # 目前節點
        # 開始循環
        while cur != None:
            # 先保留目前節點的下一個資訊 防止連結清單斷裂
            next = cur.next
            # 讓目前節點指向前一個節點
            cur.next = pre
            # 移動指針
            pre = cur
            cur = next
        return pre

2.3 合并兩個排序的連結清單

2.3.1 題目

輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。

2.3.2 思路1

思路：

如何合并呢？兩個排序的連結清單？是否要比較連結清單内元素的大小？關鍵應該還是指向的問題！
如果逐個元素兩兩比較是不是太麻煩了？應該有其餘的方法！在兩個連結清單上分别設指針？思路沒問題！但是稍微修改下！

代碼思路：

非遞歸版本
一開始先定義一個空的節點！然後讓pHead指向它！這樣就能很好地解決最後不知道傳回誰的問題！直接傳回pHead.next 逐個列印出來就行了！
中間的判斷循環語句和自己一開始的思路一緻不難！誰元素小指向誰！并且它還要移動！
最後需要做一個判斷的就是有可能一個連結清單中元素為空了！那麼這時候全部指向另一個就ok！
中間有一個細節就是 tmp = tmp.next 具體原因上面解釋了！
最後傳回的是 pHead.next 記住這個trick！

2.3.3 代碼1

非遞歸版本代碼：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 傳回合并後清單
    def Merge(self, pHead1, pHead2):
        # write code here
        # 先考慮特殊情況
        #初始化
        tmp = ListNode(0)
        pHead = tmp # pHead指向tmp
        # 開始循環
        while pHead1 and pHead2: # 均非空
            if pHead1.val < pHead2.val: # 如果1的元素小于2的 改變1
                tmp.next = pHead1 # 讓初始tmp指向1
                pHead1 = pHead1.next # 移動1
            else: # 如果1的元素大于2的 改變2
                tmp.next = pHead2 # 讓初始tmp指向2
                pHead2 = pHead2.next # 移動2
            tmp = tmp.next # 同時tmp每一次循環結束後都要向前移動一次！因為之後都要指向新元素 是以要移動到目前的位置！
        # 循環結束 看哪一個為空
        if not pHead1: # 如果pHead1為空 那麼tmp直接下一步指向2
            tmp.next = pHead2
        if not pHead2: # 如果pHead2為空 那麼tmp直接下一步指向1
            tmp.next = pHead1
        return pHead.next # 最後傳回誰呢？為什麼傳回pHead.next？可以一個一個的列印出來！

2.3.4 思路2

遞歸版本圖解：

劍指offer | 連結清單問題彙總1 前言2 題目參考

2.3.5 代碼2

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 傳回合并後清單
    def Merge(self, pHead1, pHead2):
        # write code here
        # 先考慮特殊情況
        if pHead1 is None:
            return pHead2
        if pHead2 is None:
            return pHead1
        # 開始循環遞歸判斷！
        if pHead1.val < pHead2.val: # 1元素小于2 
            pHead1.next = self.Merge(pHead1.next,pHead2) # 讓1指向除了1+2的新的兩個連結清單 
            return pHead1 # 最後傳回pHead1？妙！
        else:
            pHead2.next = self.Merge(pHead1,pHead2.next)
            return pHead2

代碼思路：

這個遞歸版本思路太妙了！
怎麼想呢？就是說每次比較兩個元素之後，不局限于元素之間的指向轉變！而是直接将小的元素指向一個新的兩個連結清單！遞歸實作！

以[1 3 ] [2 4 ] 來示例：

進入循環：

pHead1.next = self.Merge(pHead1.next,pHead2)=[3,5],[2,4,6]
					= 進入第二個循環

pHead2.next = self.Merge(pHead1,pHead2.next)=[3,5],[4,6]
           = 進入第一個循環

pHead1.next = self.Merge(pHead1.next,pHead2)=[5],[4,6]
					= 進入第二個循環

pHead2.next = self.Merge(pHead1,pHead2.next)=[5],[6]
           = 進入第一個循環

pHead1.next = self.Merge(pHead1,pHead2.next)=[None],[6]
           	= 6

直接從圖形角度了解吧！逆推推不回去！就想着每次會多出一個元素出來！
return 1 還是 2 取決于第一次進入的是哪個部分裡面！不要過多糾結于每一步的細節！從圖形角度了解就ok！

2.4 兩個連結清單的第一個公共結點

2.4.1 題目

輸入兩個連結清單，找出它們的第一個公共結點。

2.4.2 思路

思路：

直接搜尋！要不要先排序呢？然後二分查找？但是排序的複雜度會比較高吧？是的！
先暴力搜尋！先固定一個連結清單的一個元素，然後周遊另外一個連結清單，再換另一個元素！

寫了代碼，但是測試用例有點一臉懵逼，

劍指offer | 連結清單問題彙總1 前言2 題目參考

測試用例說明這個題目的意思是公共節點之後的元素都一樣！

a = {1,2,3,6,7}

b = {4,5,6,7}

圖解就是：

劍指offer | 連結清單問題彙總1 前言2 題目參考

這時候采用一種思路：

先讓把長的連結清單的頭砍掉，讓兩個連結清單長度相同，這樣，同時周遊也能找到公共結點。此時，時間複雜度O(m+n)，空間複雜度為O(MAX(m,n))。

2.4.3 代碼

代碼為：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        # 下面這個沒問題 先判斷特殊情況
        if pHead1 == None or pHead2 == None:
            return None
        cur1, cur2 = pHead1, pHead2
        while cur1 != cur2:
            cur1 = cur1.next if cur1 != None else pHead2
            cur2 = cur2.next if cur2 != None else pHead1
        return cur1

這種做法代碼看起來其實有點炫，我們來分解一下，如何讓兩個長度不同的連結清單并駕齊驅的？

2.4.4 圖解

其實四張圖就可以解釋！圖解如下：

劍指offer | 連結清單問題彙總1 前言2 題目參考

2.5 複雜連結清單的複制

2.5.1 題目

輸入一個複雜連結清單（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），傳回結果為複制後複雜連結清單的head。（注意，輸出結果中請不要傳回參數中的節點引用，否則判題程式會直接傳回空）

2.5.2 思路

思路：

完全沒有思路，啥意思？複制連結清單？咋複制？而且這個連結清單還很奇怪，兩個指向，一個是下一個節點，一個是任意一個節點？蜜汁操作！什麼叫複制？以及傳回head頭結點？

思路還是比較6的：

我們這裡将複雜連結清單的複制過程分解為三個步驟。在寫代碼的時候我們每一步定義一個函數，這樣每個函數完成一個功能，整個過程的邏輯也就非常清晰明了了。

我們這裡采用三步：

第一步：複制複雜指針的label和next。但是這次我們把複制的結點跟在元結點後面，而不是直接建立新的連結清單；
第二步：設定複制出來的結點的random。因為新舊結點是前後對應關系，是以也是一步就能找到random；
第三步：拆分連結清單。奇數是原連結清單，偶數是複制的連結清單。

2.5.3 圖解

圖解為：

劍指offer | 連結清單問題彙總1 前言2 題目參考

2.5.4 代碼

代碼為：

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 傳回 RandomListNode
    def Clone(self, pHead):
        
        # 邊界條件：如果為空連結清單 傳回空
        if not pHead:
            return None
        
        # 首先定義一個指針
        dummy = pHead
        
        # first step, N' to N next 即 複制連結清單 緊跟它後面！
        while dummy: # 爸爸非空即進入循環
            # 1 記錄爸爸的next指向
            dummynext = dummy.next
            # 2 記錄爸爸基因（label），産生兒子
            copynode = RandomListNode(dummy.label)
            # 3 讓兒子指向爸爸的next指向
            copynode.next = dummynext
            # 4 讓爸爸指向兒子
            dummy.next = copynode
            # 5 讓爸爸繼續向前 指向本應該的next
            dummy = dummynext
        
        # 複制完成 重新歸一化dummy
        dummy = pHead
         
        # second step, random' to random' 即确定random的指向
        while dummy:
            # 1 先記錄父親的random位置
            dummyrandom = dummy.random
            # 2 讓兒子指向爸爸的next位置
            copynode = dummy.next
            # 3 如果存在父親的random位置就讓兒子的random也複制一下
            if dummyrandom:
                copynode.random = dummyrandom.next
            # 4 重點：如何讓父親繼續走？讓父親指向兒子的next節點即可！
            dummy = copynode.next
        
        # third step, split linked list 分開list 奇數為真實 偶數為複制的！即如何傳回copynode
        # 其實就是确定新的指向！新的連結清單指向順序！
        # 複制random完成 重新歸一化dummy
        dummy = pHead
        # 爸爸的next指向兒子頭結點copyHead！
        copyHead = pHead.next  
        while dummy:
            # 隻要爸爸不為空 進入循環！
            # 1 産生兒子-爸爸dummy的next
            copyNode = dummy.next
            # 2 dummynext記錄爸爸實際的next指向-copyNode.next
            dummynext = copyNode.next
            # 3 讓爸爸跳到實際的next指向上
            dummy.next = dummynext
            # 4 如果dummynext非空 那麼兒子的下一個指向為dummynext的next指向
            if dummynext:
                copyNode.next = dummynext.next
            else:
                copyNode.next = None
            # 5 讓父親指向實際的下一個位置 繼續循環！
            dummy = dummynext
        return copyHead

2.6 連結清單中環的入口結點

2.6.1 題目

給一個連結清單，若其中包含環，請找出該連結清單的環的入口結點，否則，輸出null。

2.6.2 思路

思路：

周遊連結清單！
什麼情況下會包括環呢？也就是某一個節點的next指向前面的任一節點！這時候輸出該節點？
如何判斷某一個節點的next指向前面的任一節點？其實指向後面的節點也ok！就是不指向下一個！如何判斷呢？好難啊！不好想~

牛逼的思路：

分為兩部分。一個結論+如何确定連結清單環中元素的個數！
結論：如果一個連結清單有環，且環中元素的個數為n，那麼定義兩個指針，一個指針先走n步，另一個指針在原點位置，然後同時開始移動兩個指針，直至兩個指針相遇，相遇的元素即為環的入口節點！

2.6.3 圖解

具體見下圖：

劍指offer | 連結清單問題彙總1 前言2 題目參考

如何确定環内元素的個數呢？使用**快慢指針**！定義兩個指針，一前一後，一個移動2步，一個移動1步，兩個指針肯定會相遇，具體見下圖：

劍指offer | 連結清單問題彙總1 前言2 題目參考
相遇之後隻使用一個指針開始繼續向前走，一直到又走到這個位置的時候，記錄下走了多少次，即為環内元素個數！
如果判斷沒有環呢？如何判斷？那就是快慢指針的時候沒有相遇！此時就沒有環了！

2.6.4 代碼

下面開始寫代碼：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead:
            return None
       
        # 1 首先定義快慢指針 确定是否有環以及環内元素個數
        # 1.1 定義指針 注意一開始要選擇不同的
        slow = pHead
        fast = pHead.next
        # 1.2 快慢指針開始周遊 直至相遇
        while slow != fast:
        	# 注意考慮邊界情況！就是隻有一個節點！肯定也不會有環！
            if slow.next == None or fast.next == None:
                return None
            else:
            	# 慢指針一次走一步 快指針一次兩步
                slow = slow.next
                fast = fast.next.next
        # 1.3 相遇 用一個指針去走 直至回來
        tmp = slow
        n = 1
        while tmp.next !=  slow:
            n += 1
            tmp = tmp.next
        # 1.4 确定了環内元素個數 
		
		# 2 再定義兩個指針！确定入口結點
		# 2.1 定義兩個指針
        cur1 = pHead
        cur2 = pHead
        # 2.2 先移動cur2往前n步
        for i in range(n):
            cur2 = cur2.next
        # 2.3 現在開始同步移動 直至兩者相等
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        return cur1

2.7 删除連結清單中重複的結點

2.7.1 題目

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

2.7.2 思路1

這個思路超牛逼！

先将每個元素過一遍！然後統計出現的次數！過濾掉元素大于1的！
然後再将剩餘的元素組織成連結清單的形式！
完美！

2.7.3 代碼1

思路比較清晰！開始寫代碼：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        res=[]
        while pHead:
            res.append(pHead.val)
            pHead=pHead.next
        res=list(filter(lambda c:res.count(c)==1,res))
        
        newList=ListNode(0)
        pre=newList
        for i in res:
            node=ListNode(i)
            pre.next=node
            pre=pre.next
        return newList.next

2.7.4 思路2

思路：

已經排序了，那就直接周遊每一個元素吧！如果遇到相同的，都删了關鍵就是得确定指向的問題！是以應該至少要有2個指針！保留重複元素的最後一個元素的next指向，讓首個重複元素前面元素指向該next指向即可！遇到重複的就一直往下走！直到不等于！while！

思路更新：

其實思路和自己想的基本差不多隻不過有些細節需要注意
首先得建立一個first，作為最初始！其指向head！
定義一個指針跟着pHead跑！因為要考慮其前面的元素！！！！
進入循環直接考慮兩個元素是否相等，相等取出元素來進行周遊循環，然後讓之前的前一個指針指向它，即在判斷的時候隻用自身以及next來判斷就好！保持前指針last的純粹性！
最後傳回是誰也很重要！為什麼不傳回pHead？因為第一個元素無法顯示！沒有指向第一個元素的！而pHead是最後一個。為什麼不傳回last，因為沒有指向第一個元素！隻有first符合條件！

2.7.5 代碼2

代碼2：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        # 特殊情況
        if not pHead:
            return None
        # 得定義一個指針跟着pHead跑！因為要考慮其前面的元素！
        first=ListNode(-1)
        first.next=pHead
        last=first
        
        while pHead and pHead.next:
            # 開始一次判斷
            if pHead.val == pHead.next.val:
                # 如果兩個元素相等 則往後繼續移動-取出值來 做判斷依據
                val = pHead.val
                while pHead and pHead.val == val:
                    pHead = pHead.next
                # 循環結束 說明此時跳出了重複元素 改變指向
                last.next = pHead
            else:
                # 說明元素不等 繼續往前移動
                last = pHead
                pHead = pHead.next
        return first.next

參考

https://blog.csdn.net/c406495762/article/details/79247243

劍指offer | 連結清單問題彙總1 前言2 題目參考

連結清單問題彙總

1 前言

2 題目

2.1 連結清單中倒數第k個結點

2.1.1 題目

2.1.2 思路

2.1.3 代碼

2.2 反轉連結清單

2.2.1 題目

2.2.2 思路

2.2.3 代碼

2.3 合并兩個排序的連結清單

2.3.1 題目

2.3.2 思路1

2.3.3 代碼1

2.3.4 思路2

2.3.5 代碼2

2.4 兩個連結清單的第一個公共結點

2.4.1 題目

2.4.2 思路

2.4.3 代碼

2.4.4 圖解

2.5 複雜連結清單的複制

2.5.1 題目

2.5.2 思路

2.5.3 圖解

2.5.4 代碼

2.6 連結清單中環的入口結點

2.6.1 題目

2.6.2 思路

2.6.3 圖解

2.6.4 代碼

2.7 删除連結清單中重複的結點

2.7.1 題目

2.7.2 思路1

2.7.3 代碼1

2.7.4 思路2

2.7.5 代碼2

參考

繼續閱讀