Remove Nth Node From End of List

发表于 | 分类于

[Leetcode] Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example:

1
2
3
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，当第一个指针到达末尾时，第二个指针就是到要删除的节点前面。

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

        p2.next=p2.next.next

        return head