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

2019-09-19

用python语言解答LeetCode的19题

这道题目前有六种方法解法，本文目前只重点解析了常用的两种方法（方法二和方法三），后面会根据学习进度补齐其他解法的详细分析。

方法一：将链表转列表处理，之后再转链表输出
方法二：扫描两次，第一次获得链表长度，第二次执行删除操作
方法三：快慢指针法
方法四：遍历一遍链表，用字典辅助进行删除操作
方法五：利用堆栈，但是会用到负数索引，故不算是遍历一次链表
方法六：递归，目前还不知道怎么操作，有这个思路，后期会回来学习补上

碎碎念（不用看！下一节开始才是重点~~~）：

如果要是数组的话，那就好处理了，不过应该不会遇到这种考题。。。
链表能不能逆序遍历？关键是题目给的是倒数第N个节点至少需要遍历两遍吧。

第一步，遍历链表，设置计数器记录链表的结点数，
第二步，然后再怎么算出这个数的正序数，
第三步，再次遍历链表，用计数器计数，找出要删除的这个数。

思路就是这么个思路，代码不会写。。。

方法一：

先将链表转list处理再转链表输出

方法二：

如果没有扫次数限制的话，就是我想到的那个思路，第一趟扫描获得链表长度L，然后删除从前往后的第L-N+1个节点。

但是如果题目说了使用一趟扫描实现删除操作，那这个方法就不行啦~

下面来具体谈谈这个方法。我们注意到这个问题可以容易地简化成另一个问题：删除从列表开头数起的第（L-N+1）个结点，其中L是链表的长度，只要我们找到链表的长度L，这个问题就很容易解决。

算法思路：

首先我们添加一个哑结点作为辅助，该结点位于链表头部。哑结点用来简化某些极端情况，例如链表中只含有一个节点，或需要删除链表的头部。在第一次遍历中，我们找出链表的长度L。然后设置一个指向哑结点的指针，并移动它遍历链表，直至它到达第（L-N）个结点那里。我们把第（L-N）个结点的next指针重新链接至第（L-N+2）个结点。完成这个算法。

上述算法的过程如图所示：

avatar

方法二的代码：


    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution:
        def __init__(self):
            self.head = ListNode(0)
        def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
            p = self.head
            p.next = head
            length = 0
            while p:
                p = p.next
                length += 1

            p = self.head
            target = 0
            while True:
                if target == length - n - 1:
                    p.next = p.next.next
                    return self.head.next
                p = p.next
                target += 1

方法二的运行结果：

avatar

方法三：快慢指针法

典型的利用双指针法解题。
首先让指针first指向头结点，然后让其向后移动n步，接着让指针sec指向头结点，并和first一起向后移动。

当first的next指针为NULL时，sec即指向了要删除节点的前一个节点，接着让first指向的next指针指向要删除节点的下一个结点即可。

注意如果要删除的结点是首节点，那么first向后移动结束时会为NULL，这样加一个判断其是否为NULL的条件，若为NULL则返回头结点的next指针。

其实这个方法又叫快慢指针法，first指针是快指针，sec为慢指针，快指针先走N步，然后快慢指针一起走，当快指针指向链表尾部的最后一个元素时，慢指针指向元素的下一个元素就是需要删除的那个元素。

为啥要这么操作嘞，因为倒数第N个节点，与最后一个节点的间隔是固定的（N-1）。所以这里先将快指针和慢指针同时指向头结点，然后快指针移动N步，使得两个指针的间隔为N-1.之后两个指针同步后移，当快指针直到最后的时候，慢指针则指向了要删除节点的前一个节点，此时该指针只需要跳过这个结点即可完成删除操作。

再换一种解释，假设链表长度为L，定义一个指针先走N步，此时该指针还剩下L-N个节点即可完成该链表的遍历。而第L-N个节点就是题目要求的要删除的倒数第N个节点，此时只需要再定义一个指针，让它与之前的指针同时遍历，当第一个指针遇到空节点时（NULL节点)，该指针即指向删除的结点。

值得注意的是，指向应当删除的结点并无法删除它，故应该指向该删除节点的前一个节点。

伪代码：

定义一个快指针first，一个慢指针second，并将这两个指针都指向头结点
快指针先走N步
判断快指针的下一个指针是否指向空指针，若指向空指针，这说明倒数第N个元素是正向数的第一个节点，返回第一个结点的下一个结点即可执行删除第一个节点的操作（题目说了给定的n是保证有效的，所以不用多做考虑）
此时快指针和慢指针同步向后移动，直到快指针指向最后一个节点
将慢指针

下面演示了该解法的操作过程：

avatar
avatar
avatar

方法三（快慢指针法）的代码：


    #coding:utf-8

    # 用快慢指针法解决删除链表中倒数第N个元素的问题
    class ListNode():
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution():
        def removeNthFromEnd(self, head, n):
            """

            :param head: ListNode
            :param n: int
            :return: ListNode
            """
            # 设置两个指针，均指向头结点
            first = second = head
            # 快指针先移动N步
            for _ in range(n):
                first = first.next
            # 当极端情况下，即first指向了最后一个节点，且要删除的是第一个节点（倒数第N个）
            if not first:
                return head.next
            # 将两个指针同步移动
            # 直到first指向了最后一个节点（两个指针始终保持相同的间隔N-1）
            while first.next:
                first = first.next
                second = second.next
            second.next = second.next.next
            return head

方法三（快慢指针法）的运行结果：

avatar

方法四（一个博客里的思路）：

遍历一遍链表，用一个字典，记录每一步的结点，当遍历完成以后就知道倒数第N个元素的位置，然后可以在字典中找出来，删除该元素，将字典转换成链表返回，这样空间复杂度会变高

其实本质上和方法一是一样的，只不过方法一是将链表转换为列表，而这个方法是将链表转换成字典。

方法四的代码：


    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution:
        def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
            c_dict = {}
            r = head
            index = 0
            while True:
                index += 1
                c_dict[index] = r
                if r.next is not None:
                    r = r.next
                else:
                    break
            if n == 1:
                if index == 1:
                    return None
                else:
                    c_dict[index - 1].next = None
                    return head
            elif n == index:
                return head.next
            else:
                c_dict[index - n].next = c_dict[index - n + 2]
                return head

方法四的运行结果：

avatar

方法五（LeetCode评论区里的思路）：

利用堆栈，将所有节点从头按顺序入栈，这个时候stack[-n]就是我们要删除的那个节点，stack[-n-1]是删除节点的前置节点。因为用到了负数的index，故不算是在一次遍历完成了题目

方法五的代码：


    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution:
        def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
            stack,node=[],head
            while(node):
                if node:
                    stack.append(node)
                    node=node.next
            if stack[-n]==head:return head.next
            prenode=stack[-n-1]
            prenode.next=prenode.next.next
            return head

方法五的运行结果：

avatar

方法六（LeetCode评论区里的思路）：递归
先专攻链表，这个后序补上

Reference：

方法四的思路来源
https://www.jianshu.com/p/5182faaf528a
快慢指针法解题思路解析（一）
http://www.imooc.com/article/289754
快慢指针法解题思路分析（二）
https://yq.aliyun.com/articles/622771
方法五和方法六的思路来源
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/comments/