Leetcode: Partition List

Partition List | LeetCode OJ

We need to maintain lower and higher lists

1. Create 2 lists for storing the nodes with lower and higher values
2. To handle corner cases efficiently use dummy head nodes
3. Iterate over the given list and append node to the lower list if its value is lower than given number otherwise append it to higher list
4. Connect the lower list to higher list and return head of lower list

Remarks:

1. O(n) time complexity for iterating the list once. Note that every problem related to lists can be solved with linear complexity as you only need to iterate over the list a constant number of times
2. O(1) space complexity for using 4 additional variables

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        a, b = ListNode(0), ListNode(-1)
        head1, head2 = a, b
        while head:
            if head.val < x:
                a.next = head
                a = a.next
            else:
                b.next = head
                b = b.next
            head = head.next
        a.next, b.next = head2.next, None
        return head1.next