Daily LeetCode Problems: Problem 86. Partition List

Smartly Sorting Linked Lists: Solving the Partition List Problem

Introduction:

Welcome back to our daily LeetCode problem-solving series! In today’s edition, we’ll tackle problem 86 titled “Partition List.” This problem involves manipulating a linked list in a specific way while maintaining the relative order of its nodes. Join us as we dissect the problem, devise an effective strategy, provide step-by-step pseudocode, explain the core concepts, and analyze the solution’s complexity.

Problem Statement:

The problem introduces us to a linked list with a head node and an integer value x. Our task is to partition the list in such a way that all nodes with values less than x are placed before nodes with values greater than or equal to x. Importantly, the relative order of nodes within each partition should be preserved.

Approach:

To solve this problem, we can create two separate linked lists — one for nodes with values less than x and the other for nodes with values greater than or equal to x. We'll iterate through the original linked list and distribute nodes to the two partitions accordingly. Finally, we'll connect the end of the "less than" partition to the head of the "greater than or equal to" partition.

Pseudocode:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        less_than_head = ListNode()
        greater_than_head = ListNode()
        less_than_tail = less_than_head
        greater_than_tail = greater_than_head
        
        current = head
        
        while current:
            if current.val < x:
                less_than_tail.next = current
                less_than_tail = less_than_tail.next
            else:
                greater_than_tail.next = current
                greater_than_tail = greater_than_tail.next
            current = current.next
        
        less_than_tail.next = greater_than_head.next
        greater_than_tail.next = None
        
        return less_than_head.next

Core Concepts:

1. We maintain two separate linked lists — one for nodes with values less than x and the other for nodes with values greater than or equal to x.
2. We traverse the original linked list and keep appending nodes to the appropriate partition.
3. After iterating through the list, we connect the end of the “less than” partition to the head of the “greater than or equal to” partition, forming the final partitioned list.

Complexity Analysis:

Let’s analyze the complexity of our solution:

• Time complexity: We traverse the original list once, so the time complexity is O(n), where n is the number of nodes in the list.
• Space complexity: We use a constant amount of extra space for pointers and temporary nodes, so the space complexity is O(1).

Full Solution

Python

class Solution:
  def partition(self, head: ListNode, x: int) -> ListNode:
    beforeHead = ListNode(0)
    afterHead = ListNode(0)
    before = beforeHead
    after = afterHead

    while head:
      if head.val < x:
        before.next = head
        before = head
      else:
        after.next = head
        after = head
      head = head.next

    after.next = None
    before.next = afterHead.next

    return beforeHead.next

Java

class Solution {
  public ListNode partition(ListNode head, int x) {
    ListNode beforeHead = new ListNode(0);
    ListNode afterHead = new ListNode(0);
    ListNode before = beforeHead;
    ListNode after = afterHead;

    for (; head != null; head = head.next)
      if (head.val < x) {
        before.next = head;
        before = head;
      } else {
        after.next = head;
        after = head;
      }

    after.next = null;
    before.next = afterHead.next;

    return beforeHead.next;
  }
}

C++

class Solution {
 public:
  ListNode* partition(ListNode* head, int x) {
    ListNode beforeHead(0);
    ListNode afterHead(0);
    ListNode* before = &beforeHead;
    ListNode* after = &afterHead;

    for (; head; head = head->next)
      if (head->val < x) {
        before->next = head;
        before = head;
      } else {
        after->next = head;
        after = head;
      }

    after->next = nullptr;
    before->next = afterHead.next;

    return beforeHead.next;
  };
};

Conclusion:

In this article, we delved into LeetCode problem 86, “Partition List.” By intelligently sorting linked list nodes based on a given value, we achieved an elegant solution while preserving the relative order of nodes within each partition. This problem exemplifies the power of linked list manipulation in algorithmic problem-solving. Keep honing your skills and stay tuned for more intriguing LeetCode challenges in our daily series. Happy coding!