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

written at 20/06/02

题目描述

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

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

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

说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

Solution 1: 因为需要一趟扫描实现，最直观的思路就是利用递归先正向搜一遍，反向回溯的时候进行所需操作的处理。（ 注意： 需要注意当需要删除第一个元素的时候，因为给定的链表是不带空头指针的，为了方便可以加个空的头指针）
Solution 2: 利用链表的时间差遍历。即一个快速链表先遍历个节点，然后另一个慢速链表再开始遍历，则快速链表遍历完后，慢速链表所指定的位置便是倒数第个节点

代码

Solution 1

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def serach_and_delete(self, now, n):
        if now.next == None:
            return 1
        reposition = self.serach_and_delete(now.next, n) + 1
        if reposition == n+1:
            now.next = now.next.next
        return reposition
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        blank_node = ListNode(0) # mark
        blank_node.next = head
        self.serach_and_delete(blank_node, n)
        return blank_node.next

Solution 2

# 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):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        blank_node = ListNode(0) # 添加空白头指针
        blank_node.next = head
        fast_list = blank_node
        for _ in range(n):
            fast_list = fast_list.next
        slow_list = blank_node
        while fast_list.next != None:
            fast_list = fast_list.next
            slow_list = slow_list.next
        slow_list.next = slow_list.next.next
        return blank_node.next