LeetCode-19. Remove Nth Node From End of List

[ninehills]

问题

https://leetcode.com/problems/remove-nth-node-from-end-of-list/tabs/description

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.

思路

双指针：

• 先用root指针放到head之前，后续返回链表用
• first指针 从root往后走n步
• first, second 指针同时往后走，直到first到达链表尾部（first.next == None)，此时second.next 就是要去掉的Node
• 去掉second.next，然后返回root.next

解答

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __str__(self):
        return "Node({0}->[{1}])".format(self.val, self.next)

def init_list(l):
    before = None
    for i in l[::-1]:
        n = ListNode(i)
        n.next = before
        before = n
    return n

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        root = ListNode(None)
        root.next = head

        first = root
        second = root
        for i in range(n):
            first = first.next
        while first.next != None:
            first = first.next
            second = second.next
        second.next = second.next.next
        return root.next

print Solution().removeNthFromEnd(init_list([1,2,3,4,5]), 2)

[ninehills]

4 20170728