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 = None
class 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
- 加入哑节点的方法：<u>p1先走n+1步，当p1走到None的时候</u>，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
