题目描述:
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1,2], n = 1
输出:[1]
我们知道,如果只遍历一次链表,我们最多只能知道链表的长度,所以常规做法就是遍历两次,第一次获取长度。长度知道后,第二次遍历时就知道去第几个位置了。但显然,这不满足进阶要求:使用一趟扫描。
我们说的遍历,其实都是默认单指针——所以要想一次扫描获取更多的信息,就是用双指针来做。要找到倒数第N个节点的,我们就直接让两个指针之间的差为N,这样当快指针到达终点时,慢指针所在的位置就是要删除的节点了。当然,要删除某个节点,只知道它的位置是不够的,我们还需要知道这个指针的前一个节点,所以相应的节点也得进行记录。
代码:
class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ pre = ListNode()#定义一个超节点 pre.next = head#把超节点指向头节点 pp = pre#定义pp暂存超节点的值,因为后续pre值要变化 left = head#left和right就是快慢指针,也可以理解成左右指针,一个意思 right = head for i in range(n-1):#快指针要先到达比慢指针领先的n位 right=right.next while right.next:#快慢指针同时前进,直到快指针到达终点处 pre=pre.next#pre就是一直在慢指针的前一个位置,一直前进 left=left.next#慢指针也一直前进 right=right.next#快指针一直前进 pre.next = pre.next.next#删除慢指针所在的节点 return pp.next#返回超节点的next
这里道题定义了pre超节点,超节点是做链表问题的一大常用技巧,它可以避免我们以head头节点作为记录时,头节点自身被删除的情况,超节点有一个“置身事外”的功能和特点。