86. Partition List

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/partition-list
• topics: Linked List

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Idea

Most simple is to use 2 new lists and then link them together

class Solution(object):
    def partition(self, head: ListNode, x: int) -> ListNode:
 
        # before and after are the two pointers used to create two list
        # before_head and after_head are used to save the heads of the two lists.
        # All of these are initialized with the dummy nodes created.
        before = before_head = ListNode(0)
        after = after_head = ListNode(0)
 
        while head:
            # If the original list node is lesser than the given x,
            # assign it to the before list.
            if head.val < x:
                before.next = head
                before = before.next
            else:
                # If the original list node is greater or equal to the given x,
                # assign it to the after list.
                after.next = head
                after = after.next
 
            # move ahead in the original list
            head = head.next
 
        # Last node of "after" list would also be ending node of the reformed list
        after.next = None
        # Once all the nodes are correctly assigned to the two lists,
        # combine them to form a single list which would be returned.
        before.next = after_head.next
 
        return before_head.next