python鍊錶的反轉方式是什麼

python鍊錶的反轉

反轉鍊錶

給你單鍊錶的頭節點head ，請你反轉鍊錶，並返回反轉後的鍊錶。

• 輸入：頭 = [1,2,3,4,5]

• 輸出： [5,4,3,2,1]

• #輸入：頭 = [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

好了，抓住几个关键点：

• cur：原链表的头节点，在反转结束时，cur指向pre的下一个节点

• pre：原链表的尾节点，也就是反转后链表的头节点。最终返回的是pre。

• while cur：表示反转循环的条件，这里是判断cur是否为空。也可以根据题目的条件改成其他循环条件

• 反转链表的尾节点，这里的尾节点是None，后面会提到显式指定。

以上是python鍊錶的反轉方式是什麼的詳細內容。更多資訊請關注PHP中文網其他相關文章！