LeetCode 解题报告 (19)-- 从后往前删除链表第 n 个元素

发表于 标签 ， ，

原题如下：
>Given a linked list, remove the nth node from the end of list and return its head.

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.

Note:
Given n will always be valid.
Try to do this in one pass.

题目比较容易理解，就是删除从后往前数的第 n 个节点。一开始想到的方法就是先找出链表元素总数 num，再删除第 num-n+1 个元素即可。实现方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):  
    def removeNthFromEnd(self, head, n):  
        """  
        :type head: ListNode  
        :type n: int  
        :rtype: ListNode  
        """  
        nextNode = head.next  
        num = 1  
        while not nextNode == None:  
            num +=1  
            nextNode = nextNode.next

        delete = num-n+1  
        if delete == 1:  
            return head.next

        else:  
            currNode = head  
            i = 1  
            while i<delete-1:  
                currNode = currNode.next  
                i+=1  
            currNode.next = currNode.next.next  
        return head

这种方法虽然能 AC，但是题目提示了 Try to do this in one pass, 也就是这道题目存在只需遍历一遍的解法。在网上查找后发现可以先让一个指针 p1 从 head 向后移动 n 个 node，然后另外一个指针 p2 此时从 head 出发和 p1 一起移动，当 p1 移动到最后一个节点时，p2 后面的一个元素即为需要删除的元素。实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):  
    def removeNthFromEnd(self, head, n):  
        """  
        :type head: ListNode  
        :type n: int  
        :rtype: ListNode  
        """

        p1=head  
        i = 1  
        while i<=n:  
            p1 = p1.next  
            i += 1  
        p2 = head  
        while not p1.next==None:  
            p1 = p1.next  
            p2 = p2.next  
        p2.next =p2.next.next  
        return head

但是在提交时出错，排查后发现上述代码删除的 node 刚好是 head 时会出错，因为是从 1 开始往后 n 步，当删除的 node 是 head 是，n 是所有节点的数目，而此时会导致 p1 为 None，然后 p1.next 自然会报错。

解决方法是增加一个无意义的 node 指向 head，从这个 node 开始遍历即可。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:  
    def removeNthFromEnd(self, head, n):  
        """  
        :type head: ListNode  
        :type n: int  
        :rtype: ListNode  
        """  
        dummy=ListNode(0)  
        dummy.next=head  
        p1=p2=dummy  
        for i in range(n):  
            p1=p1.next  
        while p1.next:  
            p1=p1.next  
            p2=p2.next  
        p2.next=p2.next.next  
        return dummy.next

除了上面的解决方法，一开始还想过通过将链表反转再删除第 n 个 node 即可，但是题目意思是删除这个 node 不能改变其他 node 原来的排序。虽然不符合题意，但是这里一并附上代码记录链表反转的一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):  
    def removeNthFromEnd(self, head, n):  
        """  
        :type head: ListNode  
        :type n: int  
        :rtype: ListNode  
        """

        preNode  = head  
        nextNode = head.next  
        tmp = None  
        while not nextNode == None:  
            preNode.next = tmp  
            tmp = preNode  
            preNode = nextNode  
            nextNode = nextNode.next  
        preNode.next = tmp  
        head = preNode  
        if n==1:  
            return head.next  
        else:  
            i = 1  
            while i < n-1:  
                nextNode = nextNode.next  
                i += 1  
            nextNode.next = nextNode.next.next  
            return head