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