LeetCode. Remove Nth Node From End of List [Linked List]

Problem:

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

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.

 

-Summary-

1. First, create two dummy variables pointing to the head and copied dummy.

2. Calculate the head length

3. Once we face the item that next item needed to be removed, point the current item to next.next.

풀고나서 정답을 보니, one pass 로 풀수 있는 방법도 있었다.

 

Approach 2: One pass algorithm

Algorithm

The above algorithm could be optimized to one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by n+1n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by nn nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the nnth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node.

 

leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/8802/3-short-Python-solutions

class Solution:
    def removeNthFromEnd(self, head, n):
        fast = slow = head
        for _ in range(n):
            fast = fast.next
        if not fast:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]