删除链表的倒数第N个节点

中英题面

给定一个链表，删除链表的倒数第 n个节点并返回头结点。

Given a linked list, remove the nth node from the end of list and return its head.

例如，

给定一个链表: 1->2->3->4->5, 并且 n = 2.

　　当删除了倒数第二个节点后链表变成了 1->2->3->5.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

　　   After removing the second node from the end, the linked list becomes 1->2->3->5.

说明:

给的 n 始终是有效的。

尝试一次遍历实现。

Note:

Given n will always be valid.

Try to do this in one pass.
题目解读主要难点在于一次遍历完成。算法使用系统栈完成，函数递归到链表尾时开始计数并返回，数 N 个节点后删除。后来经过提醒，也可以使用两个指针模拟一个长度为 N 的队列，但笔者认为这严格意义上算两次遍历，所以还是选择了前者，算法时间复杂度 O(N)。代码

1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def removeNthFromEnd(self, head, n):
 9         """
10         :type head: ListNode
11         :type n: int
12         :rtype: ListNode
13         """
14         if (Solution.doit(self, head, n)):
15             return head.next
16         return head
17 
18     def doit(self, head, n):
19         x = y = 0
20         if (head.next):
21             x = Solution.doit(self, head.next, n)
22             if (x):
23                 y = x + 1
24         else:
25             y = 1
26         if (y == n + 1):
27             head.next = head.next.next
28             y = 0
29         return y

代码解读

注意：以下内容完全根据笔者自己对 Python 3 的理解胡说八道。

init()：class 的构造函数（？）。

self：类似 C++ 的 this。
原文链接: https://www.cnblogs.com/Efve/p/8722378.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍