腳本之家服務器常用軟件

快捷導航

python之鏈表的反轉(zhuǎn)方式

更新時間：2023年03月25日 14:18:21 作者：一葉知秋的BLOG

這篇文章主要介紹了python之鏈表的反轉(zhuǎn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

python鏈表的反轉(zhuǎn)

反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點 head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

輸入：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鏈表，依次在新的頭節(jié)點位置插入，達到反轉(zhuǎn)的效果
    """
    def reverseList(self, head: ListNode) -> ListNode:
        # 循環(huán)
        new_head = None

        while head:
            per = head.next # pre 為后置節(jié)點，及當前節(jié)點的下一個節(jié)點

            head.next = new_head # 插入頭節(jié)點元素

            new_head = head # 把串起來的鏈表賦值給頭指針

            head = per  # 向后移一個單位
        
        return  new_head  # 返回一個新的鏈表

python反轉(zhuǎn)鏈表相關技巧

給定一個單鏈表的頭結點pHead(該頭節(jié)點是有值的，比如在下圖，它的val是1)，長度為n，反轉(zhuǎn)該鏈表后，返回新鏈表的表頭。

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

輸入：

{1,2,3}

返回值：

{3,2,1}

先來看最基本的反轉(zhuǎn)鏈表代碼：

# -*- 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：原鏈表的頭節(jié)點，在反轉(zhuǎn)結束時，cur指向pre的下一個節(jié)點
pre：原鏈表的尾節(jié)點，也就是反轉(zhuǎn)后鏈表的頭節(jié)點。最終返回的是pre。
while cur：表示反轉(zhuǎn)循環(huán)的條件，這里是判斷cur是否為空。也可以根據(jù)題目的條件改成其他循環(huán)條件
反轉(zhuǎn)鏈表的尾節(jié)點，這里的尾節(jié)點是None，后面會提到顯式指定。

對于反轉(zhuǎn)鏈表的問題，抓住原鏈表的頭節(jié)點、原鏈表的尾節(jié)點、反轉(zhuǎn)循環(huán)條件、反轉(zhuǎn)鏈表的尾節(jié)點這幾個主要角色，基本沒什么問題。

接下來，舉兩個例子：

鏈表內(nèi)指定區(qū)間反轉(zhuǎn)

鏈表中的節(jié)點每k個一組翻轉(zhuǎn)

鏈表內(nèi)指定區(qū)間反轉(zhuǎn)

將一個節(jié)點數(shù)為 size 鏈表 m 位置到 n 位置之間的區(qū)間反轉(zhuǎ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的區(qū)別是，是將對整個鏈表的反轉(zhuǎn)改成鏈表 m 位置到 n 位置之間的區(qū)間反轉(zhuǎn)，來套一下公式：

原鏈表的頭節(jié)點：cur：從head出發(fā)，再走m-1步，到達cur
原鏈表的尾節(jié)點：pre：cur前面的節(jié)點
反轉(zhuǎn)循環(huán)條件：for i in range(n,m)
反轉(zhuǎn)鏈表的尾節(jié)點：需要保存下從head出發(fā)，再走m-1步，到達cur時，此時pre的位置 prePos。prePos.next是反轉(zhuǎn)鏈表的尾節(jié)點

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

需要保存下從head出發(fā)，再走m-1步，到達cur時，此時pre的位置 prePos。在反轉(zhuǎn)循環(huán)結束后，再進行穿針引線
由于不是對整個鏈表進行反轉(zhuǎn)，最好新建虛擬頭節(jié)點dummpyNode，dummpyNode.next指向整個鏈表

代碼實現(xiàn)

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

# 找到pre和cur
i = 1
while i<m:
    pre = cur
    cur = cur.next
    i = i+1
 
# 在指定區(qū)間內(nèi)反轉(zhuǎn)
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

鏈表中的節(jié)點每k個一組翻轉(zhuǎn)

將給出的鏈表中的節(jié)點每 k 個一組翻轉(zhuǎn)，返回翻轉(zhuǎn)后的鏈表

如果鏈表中的節(jié)點數(shù)不是 k 的倍數(shù)，將最后剩下的節(jié)點保持原樣

你不能更改節(jié)點中的值，只能更改節(jié)點本身。

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

輸入：

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

返回值：

{2,1,4,3,5}

套用公式

這道題目和baseline的區(qū)別是，是將對整個鏈表的反轉(zhuǎn)改成每k個一組反轉(zhuǎn)，如果節(jié)點數(shù)不是k的倍數(shù)，剩下的節(jié)點保持原樣。

先分段來看，假設面對位置1-位置k的鏈表：

原鏈表的頭節(jié)點：cur：從head出發(fā)，再走k-1步，到達cur
原鏈表的尾節(jié)點：pre：cur前面的節(jié)點
反轉(zhuǎn)循環(huán)條件：for i in range(1,k)
反轉(zhuǎn)鏈表的尾節(jié)點：先定義tail=head，等反轉(zhuǎn)完后tail.next就是反轉(zhuǎn)鏈表的尾節(jié)點

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

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的反轉(zhuǎn)鏈表。

此時：

pre：指向反轉(zhuǎn)鏈表的頭節(jié)點
cur：位置k+1的節(jié)點，下一段鏈表的頭節(jié)點
tail：反轉(zhuǎn)鏈表的尾節(jié)點

那么，得到位置k+1-位置2k的反轉(zhuǎn)鏈表，就可以用遞歸的思路，用tail.next=reverse(cur，k)

需要注意：如果鏈表中的節(jié)點數(shù)不是 k 的倍數(shù)，將最后剩下的節(jié)點保持原樣

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

代碼實現(xiàn)

完整代碼：

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

好了，抓住幾個關鍵點：