问题描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
错误解答
# 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):
def remove(node):
if not node:
return 0, node
i, _ = remove(node.next) # 先返回
if i==n:
node.next = node.next.next # 后处理
return i+1, node
return remove(head)[1]
# 这样是有问题的, 如果删除队首元素会出现问题
应该先处理, 在返回, 即返回已经删除后之后的头节点
正确解答
class Solution(object):
def removeNthFromEnd(self, head, n):
def remove(node):
if not node:
return 0, node
i, node.next = remove(node.next)
return i+1, (node, node.next)[i+1==n]
return remove(head)[1]