Solution by tanx16


  • 0
    T

    Approach #1 Partitioning (Accepted)

    Intuition

    We want to move all nodes smaller than $$x$$ to the front of the list, without disturbing the rest of the nodes. This is equivalent to taking all nodes larger than or equal to $$x$$ and moving them to the back of the list. Therefore we can traverse the list to partition it into nodes with smaller value than $$x$$ and larger or equal value to $$x$$.

    Algorithm

    Given the linked list, we first create two empty lists to contain the smaller and larger nodes. Let these lists be known as larger and smaller. In order to merge the lists at the end of the procedure, we must also create pointers to keep track of the head of each list.
    We iterate through the list. For each node we append it to smaller if the node value is smaller than $$x$$, and larger otherwise. When we reach the end of the list, we have two linked lists containing the partitioned list. The lists can be combined by appending the larger list to the smaller list, using the pointers we create in the beginning of the procedure. The resulting list is the successfully partitioned list.

    Python

    class Solution:
        def partition(self, head, x):
            if head == None or head.next == None: # Special cases
                return head
            less = ListNode(None) # Dummy node
            more = ListNode(None) # Dummy node
            head_more = more # Pointer to keep track of the list head
            head_less = less # Pointer to keep track of the list head
            while head != None:
                if head.val < x:
                    less.next = ListNode(head.val)
                    less = less.next
                else:
                    more.next = ListNode(head.val)
                    more = more.next
                head = head.next # We always go to the next node.
            less.next = head_more.next # Combine the two lists.
            return head_less.next # Remember to skip the dummy node.
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. We iterate through the list exactly once, and the concatenation procedure is in constant time.
    • Space complexity : $$O(n)$$. In the algorithm we generate a copy of each node in the list. Because we have $$2n$$, this reduces to $$O(n)$$ space. This algorithm can be modified to use $$n$$ space by mutating the list in place.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.