python之連結串列的反轉方式

2023-03-27 06:01:30

python連結串列的反轉

反轉連結串列

給你單連結串列的頭節點 head ，請你反轉連結串列，並返回反轉後的連結串列。

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

輸入：head = [1,2]
輸出：[2,1]

範例 3：

輸入：head = []
輸出：[]

題解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    解題思路：
    1.新建一個頭指標
    2.遍歷head連結串列，依次在新的頭節點位置插入，達到反轉的效果
    """
    def reverseList(self, head: ListNode) -> ListNode:
        # 迴圈
        new_head = None

        while head:
            per = head.next # pre 為後置節點，及當前節點的下一個節點

            head.next = new_head # 插入頭節點元素

            new_head = head # 把串起來的連結串列賦值給頭指標

            head = per  # 向後移一個單位
        
        return  new_head  # 返回一個新的連結串列

python反轉連結串列相關技巧

給定一個單連結串列的頭結點pHead(該頭節點是有值的，比如在下圖，它的val是1)，長度為n，反轉該連結串列後，返回新連結串列的表頭。

要求：空間複雜度 O(1)O(1) ，時間複雜度 O(n)O(n) 。

輸入：

{1,2,3}

返回值：

{3,2,1}

先來看最基本的反轉連結串列程式碼：

# -*- 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
        cur = pHead
        pre = None
        while cur:
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
        return pre

關鍵公式

抓住幾個關鍵點：

cur：原連結串列的頭節點，在反轉結束時，cur指向pre的下一個節點
pre：原連結串列的尾節點，也就是反轉後連結串列的頭節點。最終返回的是pre。
while cur：表示反轉回圈的條件，這裡是判斷cur是否為空。也可以根據題目的條件改成其他迴圈條件
反轉連結串列的尾節點，這裡的尾節點是None，後面會提到顯式指定。

對於反轉連結串列的問題，抓住原連結串列的頭節點、原連結串列的尾節點、反轉回圈條件、反轉連結串列的尾節點這幾個主要角色，基本沒什麼問題。

接下來，舉兩個例子：

連結串列內指定區間反轉

連結串列中的節點每k個一組翻轉

連結串列內指定區間反轉

將一個節點數為 size 連結串列 m 位置到 n 位置之間的區間反轉，要求時間複雜度 O(n)，空間複雜度 O(1)。

要求：時間複雜度 O(n) ，空間複雜度 O(n)

進階：時間複雜度 O(n)，空間複雜度 O(1)

輸入：

{1,2,3,4,5},2,4

返回值：

{1,4,3,2,5}

套用公式

這道題目和baseline的區別是，是將對整個連結串列的反轉改成連結串列 m 位置到 n 位置之間的區間反轉，來套一下公式：

原連結串列的頭節點：cur：從head出發，再走m-1步，到達cur
原連結串列的尾節點：pre：cur前面的節點
反轉回圈條件：for i in range(n,m)
反轉連結串列的尾節點：需要儲存下從head出發，再走m-1步，到達cur時，此時pre的位置 prePos。prePos.next是反轉連結串列的尾節點

和前面的比，需要額外注意下：

需要儲存下從head出發，再走m-1步，到達cur時，此時pre的位置 prePos。在反轉回圈結束後，再進行穿針引線
由於不是對整個連結串列進行反轉，最好新建虛擬頭節點dummpyNode，dummpyNode.next指向整個連結串列

程式碼實現

先看下套公式部分的程式碼：

# 找到pre和cur
i = 1
while i<m:
    pre = cur
    cur = cur.next
    i = i+1
 
# 在指定區間內反轉
preHead = pre
while i<=n:
    nextNode = cur.next
    cur.next = pre
    pre = cur
    cur = nextNode
    i = i+1

穿針引線部分程式碼：

nextNode = preHead.next
preHead.next = pre
if nextNode:
    nextNode.next = cur

完整程式碼：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    def reverseBetween(self , head , m , n ):
        # write code here
        dummpyNode = ListNode(-1)
        dummpyNode.next = head
        pre = dummpyNode
        cur = head
 
        i = 1
        while i<m:
            pre = cur
            cur = cur.next
            i = i+1
 
        preHead = pre
        while i<=n:
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
            i = i+1
        
        nextNode = preHead.next
        preHead.next = pre
        if nextNode:
            nextNode.next = cur
 
        return dummpyNode.next

連結串列中的節點每k個一組翻轉

將給出的連結串列中的節點每 k 個一組翻轉，返回翻轉後的連結串列

如果連結串列中的節點數不是 k 的倍數，將最後剩下的節點保持原樣

你不能更改節點中的值，只能更改節點本身。

要求空間複雜度 O(1)，時間複雜度 O(n)

輸入：

{1,2,3,4,5},2

返回值：

{2,1,4,3,5}

套用公式

這道題目和baseline的區別是，是將對整個連結串列的反轉改成每k個一組反轉，如果節點數不是k的倍數，剩下的節點保持原樣。

先分段來看，假設面對位置1-位置k的連結串列：

原連結串列的頭節點：cur：從head出發，再走k-1步，到達cur
原連結串列的尾節點：pre：cur前面的節點
反轉回圈條件：for i in range(1,k)
反轉連結串列的尾節點：先定義tail=head，等反轉完後tail.next就是反轉連結串列的尾節點

先看下套公式部分的程式碼：

pre = None
cur = head
tail = head
 
 
i = 1
while i<=k:
    nextNode = cur.next
    cur.next = pre
    pre = cur
    cur = nextNode
    i = i+1

這樣，我們就得到了1 位置1-位置k的反轉連結串列。

此時：

pre：指向反轉連結串列的頭節點
cur：位置k+1的節點，下一段連結串列的頭節點
tail：反轉連結串列的尾節點

那麼，得到位置k+1-位置2k的反轉連結串列，就可以用遞迴的思路，用tail.next=reverse(cur，k)

需要注意：如果連結串列中的節點數不是 k 的倍數，將最後剩下的節點保持原樣

i = 1
tmp = cur
while i<=k:
    if tmp:
        tmp = tmp.next
    else:
        return head
    i = i+1

程式碼實現

完整程式碼：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    def reverseKGroup(self , head , k ):
       
        # write code here
        return self.reverse(head, k )
    
    def reverse(self , head , k ):
        pre = None
        cur = head
        tail = head
 
        i = 1
        tmp = cur
        while i<=k:
            if tmp:
                tmp = tmp.next
            else:
                return head
            i = i+1
        
        i = 1
        while i<=k:
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
            i = i+1
 
        tail.next = self.reverse(cur, k)
        return pre

好了，抓住幾個關鍵點：