【leetcode-Python】-快慢指针- 19. Remove Nth Node From End of List

题目链接

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

题目描述

给定一个链表,删除链表的倒数第n个节点后返回链表的头节点。

示例

输入:head = [1,2,3,4,5],n=2

输出:[1,2,3,5]

【leetcode-Python】-快慢指针- 19. Remove Nth Node From End of List

解题思路一

此题可以借助快慢指针,一次遍历就得到结果。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)。

 

 

上一篇:CSS nth-child与nth-of-type的区别


下一篇:CSS3选择器 :nth-child()的用法