19. 删除链表的倒数第N个节点
题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
知识点
解题
- 只遍历一遍就可以知道倒数第n个数据的值。
- 直观的想法是：先遍历一遍知道总数量m，然后再走一遍，走m-n步就走到了要删除节点的前一个节点删除即可。
- 更好点的做法：使用两个指针p1,p2，p1先走n步，然后一起走，当p1走到最后的节点（p1->next is None），p2恰好走到要删除节点的前一个.
class ListNode(object): def __init__(self, x): self.val = x self.next = Noneclass Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ h1 = head h2 = head for i in range(n): h1 = h1.next while h1.next is not None: h1 = h1.next h2 = h2.next h2.next = h2.next.next return head复制代码
- 这种解法的bug：如果是删掉链表的第一个数，那p1要先走n步，最终为h1=None，此时
h1.next就会出错。 - 而且删掉首节点，也不能通过
h2.next = h2.next.next实现。 - 可以在此情况下在头部加入哑节点或者直接返回head.next
if h1 is None: return head.next复制代码
- 加入哑节点的方法：p1先走n+1步，当p1走到None的时候，p2走到了被删节点的前一个节点，删除节点后，返回哑节点的下一个节点
class Solution(object): def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ h = ListNode(0) h.next = head h1 = h h2 = h for i in range(n + 1): h1 = h1.next while h1 is not None: h1 = h1.next h2 = h2.next h2.next = h2.next.next return h.next复制代码