19. 删除链表的倒数第 N 个节点
给定一个链表, 删除链表的倒数第 n 个节点, 并且返回链表的头结点.
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
给定的 n 保证是有效的.
进阶:
你能尝试使用一趟扫描实现吗?
- Python most votes solution:
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution(object):
- def removeNthFromEnd(self, head, n):
- """
- :type head: ListNode
- :type n: int
- :rtype: ListNode
- """
- fast = slow = head
- for _ in range(n):
- fast = fast.next
- if not fast:
- return head.next
- while fast.next:
- fast = fast.next
- slow = slow.next
- slow.next = slow.next.next
- return head
时间复杂度:\(O(n)\)
分析:
整个算法是基于这样一种思路:
把整个链表分成两段, 一段长为 n (n=N), 另一段长为 m,(m+n)等于整个链表的总长度. 如下图所示.
为了实现只进行一趟扫描就删除倒数第 N 个节点, 需要用到两个指针: fast 和 slow.
第一次移动: 程序中的 for 循环用于将 fast 向右移动 n 个距离(假设蓝色框左侧为链表的头部, 右侧为链表的尾部), 此时 slow 并不移动, 为第二次移动做准备.
第二次移动: 程序中的 while 循环用于实现第二次移动, 此时的 slow 和 fast 是同步移动的. 如下图所示.
此时 fast 将走完剩下的距离 m, 同时 slow 也跟随 fast 向右移动 m 个距离.
第二次移动之后, fast 将指向链表中的最后一个节点, slow 将指向倒数第 N 个节点前面紧邻的一个节点的位置. 此时, 只需让 slow 的下一个节点跳过倒数第 N 个节点 (即指向倒数第 N 个节点后面紧邻的一个节点) 的位置, 即可把倒数第 N 个节点删除掉.
这里要注意一种特殊情况: 即第一次移动就已经移动到了链表的最后一个节点, 此时第二次移动将不再进行, 从而无法删除掉倒数第 N 个节点. 一种解决方法是: 在第一次移动结束之后, 判断 fast 是否已经移动到了最后一个节点, 如果是, 则直接 return head.next(因为这种情况就相当于是删除链表中的第一个节点); 否则执行第二次移动.
程序中修改的是 slow, 但最终 return head 就可以, 这是因为 slow 和 head 指向了同一个链表(slow = fast = head), 在这种情况下, fast,slow,head 中只要有一个发生变化, 都会影响到其他两个的值.
2-1
来源: http://www.bubuko.com/infodetail-3106404.html