https://leetcode.com/problems/remove-nth-node-from-end-of-list/
给定一个链表,删除链表的倒数第n个节点后返回链表的头节点。
输入:head = [1,2,3,4,5],n=2
输出:[1,2,3,5]
此题可以借助快慢指针,一次遍历就得到结果。fast指针先走n步,指向第n个节点(头节点为第1个节点)。slow指针指向头节点。那么fast和slow指针中间隔着n-1个节点。fast指针和slow同速前进,每次移动一位。当fast指针指向null时,slow指针会指向倒数第n个节点(fast和slow中间隔着的节点数为n-1)。
但是要想删除倒数第n个节点,我们需要让slow指向倒数第n+1个节点(即倒数第n个节点的前驱节点),这里我们借助dummy node技巧来实现。常规情况看,由于头指针的前驱指针为None,需要在代码中额外判断被删除的是否是头指针。但我们一般会使用哑节点dummy node技巧来避免这种特殊判断。我们添加一个哑节点,令它的next指针指向链表的头节点。因此我们可以让slow最开始指向dummy node,这样当fast指向null时,slow会指向倒数第n+1个节点(fast和slow中间隔着的节点数为n)。
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: dummy = ListNode(0,head) #指向head的dummy节点 fast = head slow = dummy #首先fast向前走n个节点 while(n): fast = fast.next n -= 1 #然后fast slow同步移动,直到fastnull while(fast): fast = fast.next slow = slow.next #slow为待移除节点的前驱节点 slow.next = slow.next.next return dummy.next #返回头节点,这里不能直接返回head,因为head有可能被删除了
我们也可以让fast和slow最开始都指向dummy node,然后fast先走n步,指向第n个节点(头节点为第1个节点),那么fast和slow中间隔着n-1个节点。fast和slow同速前进,当fast.next为null时,fast指向链表最后一个节点,此时start就指向倒数第n个节点的前驱节点(倒数第n+1个节点),两个指针中间隔着n-1个节点。代码实现如下:
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: dummy = ListNode(0,head) fast = dummy slow = dummy #首先fast向前走n个节点 while(n): fast = fast.next n -= 1 #然后fast slow同步移动 while(fast.next): fast = fast.next slow = slow.next #slow为待移除节点的前驱节点 slow.next = slow.next.next return dummy.next #返回头节点,这里不能直接返回head,因为head有可能被删除了
重点是我们要确保fast和slow指针在同速移动时中间隔着的节点数是符合要求的。
时间复杂度为O(L),L为链表长度。空间复杂度为O(1)。