題目
給定一個(gè)鏈表篮幢，請(qǐng)刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭節(jié)點(diǎn)为迈。
例如：
原鏈表轉(zhuǎn)換為列表：[1, 2, 3, 4, 5]三椿，需要?jiǎng)h除倒數(shù)第2個(gè)節(jié)點(diǎn)
最終的鏈表轉(zhuǎn)換為列表：[1, 2, 3, 5]原鏈表轉(zhuǎn)換為列表：[1]缺菌，需要?jiǎng)h除倒數(shù)第1個(gè)節(jié)點(diǎn)
最終的鏈表轉(zhuǎn)換為列表：[]原鏈表轉(zhuǎn)換為列表：[1, 2]，需要?jiǎng)h除倒數(shù)第1個(gè)節(jié)點(diǎn)
最終的鏈表轉(zhuǎn)換為列表：[1]
已知 鏈表節(jié)點(diǎn)的定義搜锰、鏈表與列表相互轉(zhuǎn)換 的代碼如下：
class ListNode: # 單鏈表
def __init__(self, val=0, next=None):
self.val = val # 鏈表節(jié)點(diǎn)上存儲(chǔ)的元素
self.next = next # 指向下一個(gè)鏈表節(jié)點(diǎn)
def list_to_list_node(numbers): # 將列表轉(zhuǎn)換為單向鏈表伴郁，并返回鏈表的頭節(jié)點(diǎn)
dummy_head = ListNode(0)
pre = dummy_head
for number in numbers:
pre.next = ListNode(number)
pre = pre.next
pre = dummy_head.next
return pre
def list_node_to_list(node): # 將單向鏈表轉(zhuǎn)換為列表
result = []
while node:
result.append(node.val)
node = node.next
return result
實(shí)現(xiàn)思路1
- 要?jiǎng)h除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，我們可以先計(jì)算出鏈表長(zhǎng)度length纽乱，然后再進(jìn)行處理蛾绎，假設(shè)求出鏈表長(zhǎng)度length為5
- 如果要?jiǎng)h除鏈表的倒數(shù)第 2 個(gè)節(jié)點(diǎn)，也就是第4個(gè)節(jié)點(diǎn)鸦列，此時(shí)我們只需要讓鏈表的第 3 個(gè)節(jié)點(diǎn)租冠，通過(guò) next 指向到第 5 個(gè)節(jié)點(diǎn)即可
- 有一種情況，如果要?jiǎng)h除的節(jié)點(diǎn)恰好是鏈表的頭節(jié)點(diǎn)薯嗤，這個(gè)情況在原鏈表上就不好處理顽爹，因?yàn)榍懊鏇](méi)有頭節(jié)點(diǎn)了，所以骆姐，我們統(tǒng)一設(shè)置一個(gè)虛擬頭節(jié)點(diǎn) dummy_head 進(jìn)行處理镜粤，而 dummy_head 通過(guò) next 指向原鏈表的頭節(jié)點(diǎn)就行
代碼實(shí)現(xiàn)1
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy_head = ListNode(next=head) # 設(shè)置一個(gè)虛擬頭節(jié)點(diǎn)
cur1, length = dummy_head, 0
while cur1 is not None: # 計(jì)算鏈表的長(zhǎng)度
length += 1
cur1 = cur1.next
cur2, step = dummy_head, length - 1 - n # step 表示被刪除節(jié)點(diǎn)的前一個(gè)位置，減去1是因?yàn)槎嗔艘粋€(gè)虛擬頭節(jié)點(diǎn)
while step:
cur2 = cur2.next
step -= 1
cur2.next = cur2.next.next # 跳過(guò)下一個(gè)節(jié)點(diǎn)玻褪，直接指向下下個(gè)節(jié)點(diǎn)
return dummy_head.next
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
實(shí)現(xiàn)思路2
- 使用
雙指針的方式來(lái)實(shí)現(xiàn) - 設(shè)置兩個(gè)節(jié)點(diǎn)指針：slow肉渴、fast，fast先移動(dòng) n 位带射，然后再讓slow同规、fast同時(shí)移動(dòng)，直到fast指向的下一個(gè)節(jié)點(diǎn)為空時(shí)窟社，二者均停止移動(dòng)
- 此時(shí)券勺，slow 指向的是鏈表中要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，我們只需要讓當(dāng)前節(jié)點(diǎn)通過(guò) next 指向下下個(gè)節(jié)點(diǎn)即可
代碼實(shí)現(xiàn)2
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy_head = ListNode(next=head) # 設(shè)置一個(gè)虛擬頭節(jié)點(diǎn)
slow, fast = dummy_head, dummy_head # 設(shè)置兩個(gè)節(jié)點(diǎn)指針
while n: # fast先移動(dòng) n 步
fast = fast.next
n -= 1
while fast.next is not None: # slow和fast同時(shí)移動(dòng)灿里，當(dāng)fast指向空節(jié)點(diǎn)退出循環(huán)
fast = fast.next
slow = slow.next
slow.next = slow.next.next # slow指向下下個(gè)節(jié)點(diǎn)（相當(dāng)于跳過(guò)下一個(gè)節(jié)點(diǎn)关炼，也就是倒數(shù)第N個(gè)節(jié)點(diǎn)）
return dummy_head.next
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
實(shí)現(xiàn)思路3
- 使用
棧的方式實(shí)現(xiàn)，但空間復(fù)雜度會(huì)變?yōu)?O(n) - 定義一個(gè)棧 stack匣吊，遍歷鏈表儒拂，讓所有節(jié)點(diǎn)入棧
- 要?jiǎng)h除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，只需讓 stack 執(zhí)行 n 次出棧操作色鸳，此時(shí)棧頂就恰好為待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
- 接著讓棧頂節(jié)點(diǎn)通過(guò) next 指向下下個(gè)節(jié)點(diǎn)即可
代碼實(shí)現(xiàn)3
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy_head = ListNode(next=head) # 設(shè)置一個(gè)虛擬頭節(jié)點(diǎn)
cur, stack = dummy_head, []
while cur is not None: # 所有節(jié)點(diǎn)入棧
stack.append(cur)
cur = cur.next
while n: # 執(zhí)行 n 次出棧操作
stack.pop()
n -= 1
cur = stack[-1] # 獲取棧頂元素侣灶，此時(shí)棧頂恰好為待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
cur.next = cur.next.next # 跳過(guò)下一個(gè)節(jié)點(diǎn)，直接指向下下個(gè)節(jié)點(diǎn)
return dummy_head.next
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
更多Python編程題缕碎，等你來(lái)挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
