86.Partition_List(Medium).md

86. Partition List (Medium)

Date and Time: Jan 12, 2025, 2:39 (EST)

Link: https://leetcode.com/problems/partition-list

Question:

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.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3

Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2

Output: [1,2]

Constraints:

• The number of nodes in the list is in the range [0, 200].

• -100 <= Node.val <= 100

• -200 <= x <= 200

Walk-through:

The key observation is that, every node that is less than x can be appended to the first list. Every node that is greater or equal to x can be appended to the second list. Then, we can merge this two lists together.

Python Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # Save nodes < x to the first list
        # Save nodes >= x to the second list

        # TC: O(n), n is total nodes, SC: O(1)
        first = dummyFirst = ListNode()
        second = dummySecond = ListNode()
        while head:
            if head.val < x:
                first.next = ListNode(head.val)
                first = first.next
            else:
                second.next = ListNode(head.val)
                second = second.next
            head = head.next
        # Merge first list with second list
        first.next = dummySecond.next
        return dummyFirst.next

Time Complexity: $O(n)$
Space Complexity: $O(1)$