【LeetCode每天一题】Remove Nth Node From End of List(移除链表倒数第N个节点)

偏执的太偏执、 2021-12-15 14:19 114阅读 0赞

Given a linked list, remove the n-th node from the end of list and return its head.

Example:                     Given linked list: 1->2->3->4->5, and n = 2.                     After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:                          Given n will always be valid.

Follow up:                  Could you do this in one pass?

思路

--------------------

我们采用两个指针和哨兵模式来解决这个问题。 一开始先将快指针向前移动N位，然后和慢指针一起移动，直到指针指向最后一位结束。然后将漫指针的next指针重新赋值，就可以将对应节点删除。

时间复杂度为O(n)， 空间复杂度为O(1)。

图示步骤

--------------------

![1639597-20190404105950985-1699065216.png][]

解决代码

--------------------

1 # Definition for singly-linked list.
     2 # class ListNode(object):
     3 # def __init__(self, x):
     4 # self.val = x
     5 # self.next = None
     6 
     7 class Solution(object): 8     def removeNthFromEnd(self, head, n): 9         """
    10 :type head: ListNode 11 :type n: int 12 :rtype: ListNode 13         """
    14         if not head or n == 0: 15             return head 16         res = second = first = ListNode(0) # 构建哨兵节点 17         first.next = head 18         while n > 0: # 移动快指针 19             first = first.next 20             n -= 1
    21         while first.next: # 移动快慢指针 22             second = second.next 23             first = first.next 24         second.next = second.next.next # 删除指定节点 25         return res.next

转载于:https://www.cnblogs.com/GoodRnne/p/10653691.html

[1639597-20190404105950985-1699065216.png]: /images/20211214/65111ad0c9ba4cd894bcdf688d0f0c8b.png