leetcode第19题，给定一个单链表，去除倒数第n个节点。 这个题如果只要求用两轮遍历做是很简单的，第一轮遍历先找到链表的长度，第二轮就可以找到要删除哪一个节点就可以了。这里为了避免删除头结点的情况存在，需要使用一个哑变量作为头部，这样就可以方便地解决这个问题。
def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ p = head index = 0 while p != None: index += 1 PRint index, p.val p = p.next length = index if n > length: return None index = 0 dummy = ListNode(0) dummy.next = head p = dummy while p!= None: index += 1 if index == length-n+1: p.next = p.next.next return dummy.next else: p = p.next有没有一遍遍历就可以的办法呢？使用双指针可以。声明一个哑变量做头部，两个指针都指向头部。然后第一个指针先移动n个位置，然后两个指针再一起移动，知道第一个指针跑到末尾。实际上，这就好比两个人赛跑，先拉开n个单位的差距，然后保持这个差距，等先移动的那个指针到头，后移动的指针自然就指向了要删除节点的上一个节点了。
def removeNthFromEnd2(self, head, n): dummy = ListNode(0) dummy.next = head first = dummy second = dummy for i in range(1,n+2): first = first.next while first != None: first = first.next second = second.next second.next = second.next.next return dummy.next新闻热点
疑难解答
