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

r囧r小猫 2021-10-24 05:31 228阅读 0赞

**中英题面**

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

Given a linked list, remove the *n*th 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