HomeLeetcode86. Partition List - Leetcode Solutions
Leetcode

86. Partition List – Leetcode Solutions

Declan Clarke

Description:

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.

Examples:

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]

Solution in Python:

To solve the problem of partitioning a linked list around a value x, we can use two dummy linked lists to separate the nodes less than x and those greater than or equal to x. Then, we can combine these two lists to form the desired output.

Python
# 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]:
        # Create two dummy nodes to start the less and greater lists
        less_dummy = ListNode(0)
        greater_dummy = ListNode(0)
        
        # These pointers will be used to build the new lists
        less = less_dummy
        greater = greater_dummy
        
        # Iterate through the original list
        current = head
        while current:
            if current.val < x:
                # Append to the end of the less list
                less.next = current
                less = less.next
            else:
                # Append to the end of the greater list
                greater.next = current
                greater = greater.next
            
            # Move to the next node in the original list
            current = current.next
        
        # End the greater list
        greater.next = None
        
        # Combine the two lists
        less.next = greater_dummy.next
        
        # The head of the new list is the next node of the less_dummy
        return less_dummy.next

Explanation:

  1. Dummy Nodes Initialization:
    • We initialize two dummy nodes, less_dummy and greater_dummy. These nodes will help us to easily build the two separate lists: one for nodes with values less than x and another for nodes with values greater than or equal to x.
  2. Pointers Initialization:
    • We initialize two pointers, less and greater, which will help in building the respective lists by pointing to the current end of the less and greater lists.
  3. Iteration through the Original List:
    • We iterate through the original list using a pointer current. For each node:
      • If the node’s value is less than x, we add it to the end of the less list.
      • If the node’s value is greater than or equal to x, we add it to the end of the greater list.
    • We then move the current pointer to the next node in the original list.
  4. Ending the Greater List:
    • After the loop, we set greater.next to None to terminate the greater list.
  5. Combining the Two Lists:
    • We set less.next to point to the first node of the greater list (i.e., greater_dummy.next).
  6. Returning the Result:
    • The head of the new partitioned list is the next node of the less_dummy node, i.e., less_dummy.next.

This method ensures that the relative order of nodes in each partition is preserved and the overall time complexity is O(n), where nnn is the number of nodes in the linked list.

Solution in Javascript:

JavaScript
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    // Create dummy nodes for the less and greater partitions
    let lessDummy = new ListNode(0);
    let greaterDummy = new ListNode(0);
    // Pointers for the current nodes in each partition
    let less = lessDummy;
    let greater = greaterDummy;
    
    // Traverse the original list
    let current = head;
    while (current !== null) {
        if (current.val < x) {
            // Append to the less partition
            less.next = current;
            less = less.next;
        } else {
            // Append to the greater partition
            greater.next = current;
            greater = greater.next;
        }
        // Move to the next node
        current = current.next;
    }
    
    // Terminate the greater partition
    greater.next = null;
    
    // Combine the two partitions
    less.next = greaterDummy.next;
    
    // Return the head of the less partition (ignoring the dummy head)
    return lessDummy.next;
};

Solution in Java:

Java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // Create dummy nodes for the less and greater partitions
        ListNode lessDummy = new ListNode(0);
        ListNode greaterDummy = new ListNode(0);
        // Pointers for the current nodes in each partition
        ListNode less = lessDummy;
        ListNode greater = greaterDummy;
        
        // Traverse the original list
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                // Append to the less partition
                less.next = current;
                less = less.next;
            } else {
                // Append to the greater partition
                greater.next = current;
                greater = greater.next;
            }
            // Move to the next node
            current = current.next;
        }
        
        // Terminate the greater partition
        greater.next = null;
        
        // Combine the two partitions
        less.next = greaterDummy.next;
        
        // Return the head of the less partition (ignoring the dummy head)
        return lessDummy.next;
    }
}

Solution in C#:

C#
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode Partition(ListNode head, int x) {
        // Create dummy nodes for the less and greater partitions
        ListNode lessDummy = new ListNode(0);
        ListNode greaterDummy = new ListNode(0);
        // Pointers for the current nodes in each partition
        ListNode less = lessDummy;
        ListNode greater = greaterDummy;
        
        // Traverse the original list
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                // Append to the less partition
                less.next = current;
                less = less.next;
            } else {
                // Append to the greater partition
                greater.next = current;
                greater = greater.next;
            }
            // Move to the next node
            current = current.next;
        }
        
        // Terminate the greater partition
        greater.next = null;
        
        // Combine the two partitions
        less.next = greaterDummy.next;
        
        // Return the head of the less partition (ignoring the dummy head)
        return lessDummy.next;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com