python鏈表的反轉(zhuǎn)

反轉(zhuǎn)鏈表

給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(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.新建一個(gè)頭指針
    2.遍歷head鏈表，依次在新的頭節(jié)點(diǎn)位置插入，達(dá)到反轉(zhuǎn)的效果
    """
    def reverseList(self, head: ListNode) -> ListNode:
        # 循環(huán)
        new_head = None

        while head:
            per = head.next # pre 為后置節(jié)點(diǎn)，及當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

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

            new_head = head # 把串起來(lái)的鏈表賦值給頭指針

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

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

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

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

輸入：

{1,2,3}

返回值：

{3,2,1}

先來(lái)看最基本的反轉(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

關(guān)鍵公式

抓住幾個(gè)關(guān)鍵點(diǎn)：

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

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

接下來(lái)，舉兩個(gè)例子：

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

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

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

將一個(gè)節(jié)點(diǎn)數(shù)為 size 鏈表 m 位置到 n 位置之間的區(qū)間反轉(zhuǎn)，要求時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)。

要求：時(shí)間復(fù)雜度 O(n) ，空間復(fù)雜度 O(n)

進(jìn)階：時(shí)間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)

輸入：

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

返回值：

{1,4,3,2,5}

套用公式

這道題目和baseline的區(qū)別是，是將對(duì)整個(gè)鏈表的反轉(zhuǎn)改成鏈表 m 位置到 n 位置之間的區(qū)間反轉(zhuǎn)，來(lái)套一下公式：

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

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

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

代碼實(shí)現(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é)點(diǎn)每k個(gè)一組翻轉(zhuǎn)

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

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

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

要求空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(n)

輸入：

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

返回值：

{2,1,4,3,5}

套用公式

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

先分段來(lái)看，假設(shè)面對(duì)位置1-位置k的鏈表：

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

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

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)鏈表。

此時(shí)：

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

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

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

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

代碼實(shí)現(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

好了，抓住幾個(gè)關(guān)鍵點(diǎn)：

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

想清楚這幾個(gè)關(guān)鍵點(diǎn)都是如何定義的，基本題目都可以迎刃而解啦。

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論