題目
給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
方法：雙指針?lè)?/h5>
- 設(shè)置虛頭節(jié)點(diǎn)，方便刪除頭節(jié)點(diǎn)
- 若要尋找倒數(shù)第 n 個(gè)節(jié)點(diǎn)，那么可以使得 fast 指針比 slow 指針先走 n 步，然后讓他們同步走，直至 fast 指向鏈表的末節(jié)點(diǎn)，此時(shí) slow 指向需刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
- 刪除所需刪除的節(jié)點(diǎn)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
dummy_head = ListNode(next = head)
slow = dummy_head
fast = dummy_head
while n != 0:
fast = fast.next
n = n - 1
while fast.next != None:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy_head.next
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
dummy_head = ListNode(next = head)
slow = dummy_head
fast = dummy_head
while n != 0:
fast = fast.next
n = n - 1
while fast.next != None:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy_head.next
※slow.next = slow.next.next而非slow.next = fast是因?yàn)?，后者只有?n=2 時(shí)成立
