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é)點，及當(dāng)前節(jié)點的下一個節(jié)點
head.next = new_head # 插入頭節(jié)點元素
new_head = head # 把串起來的鏈表賦值給頭指針
head = per # 向后移一個單位
return new_head # 返回一個新的鏈表
python反轉(zhuǎn)鏈表相關(guān)技巧
給定一個單鏈表的頭結(jié)點pHead(該頭節(jié)點是有值的，比如在下圖，它的val是1)，長度為n，反轉(zhuǎn)該鏈表后，返回新鏈表的表頭。
要求：空間復(fù)雜度 O(1)O(1) ，時間復(fù)雜度 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關(guān)鍵公式
抓住幾個關(guān)鍵點：
- cur：原鏈表的頭節(jié)點，在反轉(zhuǎn)結(jié)束時，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)，要求時間復(fù)雜度 O(n)，空間復(fù)雜度 O(1)。
要求：時間復(fù)雜度 O(n) ，空間復(fù)雜度 O(n)
進階：時間復(fù)雜度 O(n)，空間復(fù)雜度 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)結(jié)束后，再進行穿針引線
- 由于不是對整個鏈表進行反轉(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é)點本身。
要求空間復(fù)雜度 O(1)，時間復(fù)雜度 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é)點保持原樣。
先分段來看，假設(shè)面對位置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好了，抓住幾個關(guān)鍵點：
- cur：原鏈表的頭節(jié)點，在反轉(zhuǎn)結(jié)束時，cur指向pre的下一個節(jié)點
- pre：原鏈表的尾節(jié)點，也就是反轉(zhuǎn)后鏈表的頭節(jié)點。最終返回的是pre。
- while cur：表示反轉(zhuǎn)循環(huán)的條件，這里是判斷cur是否為空。也可以根據(jù)題目的條件改成其他循環(huán)條件
- 反轉(zhuǎn)鏈表的尾節(jié)點，這里的尾節(jié)點是None，后面會提到顯式指定。
想清楚這幾個關(guān)鍵點都是如何定義的，基本題目都可以迎刃而解啦。
總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
本文給大家分享了2則使用Python實現(xiàn)正則表達式檢測密碼合法性的代碼，由于是新手，所以方法比較笨，不過還是分享給小伙伴，希望對大家能夠有所幫助。2016-01-01
這篇文章主要介紹了Python grequests模塊使用場景及代碼實例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-08-08
Python實現(xiàn)批量更換指定目錄下文件擴展名的方法
這篇文章主要介紹了Python實現(xiàn)批量更換指定目錄下文件擴展名的方法,結(jié)合完整實例分析了Python批量修改文件擴展名的技巧,并對比分析了shell命令及scandir的兼容性代碼,需要的朋友可以參考下2016-09-09
這篇文章主要為大家詳細(xì)介紹了python實現(xiàn)象棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
Python實現(xiàn)mysql數(shù)據(jù)庫中的SQL文件生成和導(dǎo)入
這篇文章主要介紹了Python實現(xiàn)mysql數(shù)據(jù)庫中的SQL文件生成和導(dǎo)入，首先通過將mysql數(shù)據(jù)導(dǎo)出到SQL文件中展開詳細(xì)內(nèi)容需要的小伙伴可以參考一下2022-06-06
這篇文章主要為大家介紹了Python中re模塊常用方法，并對這些常用方法進行總結(jié)分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-09-09
這篇文章主要介紹了Python小技巧練習(xí)分享，文章基于python的相關(guān)內(nèi)容展開詳細(xì)的python小技巧內(nèi)容，具有一定的參考價值，需要的小伙伴可以參考一下2022-05-05
這篇文章主要介紹了Python用requests庫爬取返回為空的解決辦法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
Python如何用filter函數(shù)篩選數(shù)據(jù)
這篇文章主要介紹了Python如何用filter函數(shù)篩選數(shù)據(jù),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-03-03
Python?pyinstaller打包exe最新完整圖文教程
pyinstaller是一個非常簡單的打包python的py文件的庫,下面這篇文章主要給大家介紹了關(guān)于Python?pyinstaller打包exe的相關(guān)資料,文中介紹的非常詳細(xì),需要的朋友可以參考下2023-12-12