menu

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

Problem (Medium)

019. Remove Nth Node From End of List

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.

Follow up:

Could you do this in one pass?

Approach 1: One Pass (First Try)

Idea

The idea of one pass is to check if the n-th item past current item is None or not. If it’s None, the current item should be removed from the linked list. (Need to save the previous item’s link and watch out some special cases, i.e, the linked list is short)

Solution

    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        def jump(l, n):
            for i in range(n):
                l = l.next
            return l 

        cur, parent = head, None
        if not cur.next: 
            return

        while cur:
            if not jump(cur, n):
                if parent:
                    parent.next = cur.next
                else:
                    head = cur.next
                break
            else:
                parent = cur
                cur = cur.next
        return head

Complexity

  • Time: $O(L)$
  • Space: $O(1)$

Approach 1 Update: One Pass Two Pointers

Idea

Find another pointer p2 at position i+n if possible. Let p2 and original pointer pass in the same loop. Once p2 goes to None, then remove the current item at p1. Done!

Solution

class Solution1_update:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head.next:
            return

        p2 = head
        for i in range(n):
             p2 = p2.next
        if not p2:
            return head.next

        p1, parent = head, None
        while True:
            if not p2:
                parent.next = p1.next
                break
            else:
                parent = p1
                p1 = p1.next
                p2 = p2.next
        return head

Complexity

  • Time: $O(L)$
  • Space: $O(1)$

Approach 1: Two Pass (Find the Length of the List)

Idea

If we find the length of the list L, then the problem becomes simple: just remove the item at L - n + 1 if L >= n + 1. Watch out:

  • if L == 1: return None;
  • else, if L > 1 and L < n + 1 (actually, same as L == n), just remove the first item in the list.

Solution

class Solution2:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        L = 0
        tmp = head
        while tmp:
            tmp= tmp.next
            L += 1
        
        if not head.next:
            return
        if L == n:
            return head.next

        previous, cur = None, head

        for i in range(L - n):
            previous = cur
            cur = cur.next
        previous.next = cur.next
        return head

Complexity

  • Time: $O(L)$
  • Space: $O(1)$



KF

Comments