溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“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 # 返回一個新的鏈表
給定一個單鏈表的頭結點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 的倍數，將最后剩下的節點保持原樣
你不能更改節點中的值，只能更改節點本身。
要求空間復雜度 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鏈表的反轉方式是什么”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
