Partition List

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode less_head(0);
        ListNode greater_head(0);
        ListNode *less_ptr = &less_head;
        ListNode *greater_ptr = &greater_head;
        
        while (head != nullptr) {
            if (head->val < x) {
                less_ptr->next = head;
                less_ptr = less_ptr->next;
            } else {
                greater_ptr->next = head;
                greater_ptr = greater_ptr->next;
            }
            head = head->next;
        }
        
        greater_ptr->next = nullptr;
        less_ptr->next = greater_head.next;
        
        return less_head.next;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) { this.val = val; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode smallerHead = new ListNode(0);
        ListNode greaterHead = new ListNode(0);
        ListNode smaller = smallerHead;
        ListNode greater = greaterHead;
        
        while (head != null) {
            if(head.val < x) {
                smaller.next = head;
                smaller = smaller.next;
            } else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }
        
        greater.next = null;
        smaller.next = greaterHead.next;
        
        return smallerHead.next;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode less_head, greater_head;
    struct ListNode *less_ptr = &less_head;
    struct ListNode *greater_ptr = &greater_head;
    
    struct ListNode *curr = head;
    while (curr != NULL) {
        if (curr->val < x) {
            less_ptr->next = curr;
            less_ptr = less_ptr->next;
        } else {
            greater_ptr->next = curr;
            greater_ptr = greater_ptr->next;
        }
        curr = curr->next;
    }
    
    less_ptr->next = greater_head.next;
    greater_ptr->next = NULL;
    
    return less_head.next;
}

To solve this coding challenge effectively, we need to reorder the nodes in a linked list such that nodes with values less than a given value \( x \) appear before nodes with values greater than or equal to \( x \). Additionally, the original relative order of nodes within each partition must be preserved. We will break down the problem and create a clear plan before implementing the solution in pseudocode.

Explanation

The key steps to solving this problem involve:

Initialization : Setting up two separate pointers/lists which will collect nodes that are either less than \( x \) or greater than/equal to \( x \).
Traversal : Iterating through the original linked list to distribute nodes into these two new lists based on comparisons with \( x \).
Combination : Merging the two lists in the appropriate order.
Edge Handling : Ensuring that the new list ends correctly.

Step-by-Step Explanation:

Initialization :

Initialize two dummy nodes,
less_head

and
greater_head

, which will serve as the starting points for the two new lists.
Set two pointers,
less_ptr

and
greater_ptr

, to manage the current position in these lists.

Traversal :

Traverse the original linked list node by node.
For each node, compare its value to \( x \). If the value is less than \( x \), attach it to the
less_ptr

list; otherwise, attach it to the
greater_ptr

list.
Move the
less_ptr

or
greater_ptr

forward accordingly after attaching the node.

Combination :

After traversing all nodes, the list pointed to by
greater_ptr

might end with a
next

pointer that still points to a portion of the original list, so set its
next

to
None

.
Attach the end of the
less_ptr

list to the start of the
greater_ptr

list to merge the two.

Final Output :

The combined list is obtained by skipping the dummy node
less_head

.

Given these steps, the pseudocode can be developed as follows:

Detailed Steps in Pseudocode:

                                            
# Define the function to partition the linked list
Function partition_linked_list(head, x):
    
    # Initialize dummy nodes to start two new lists
    less_head = Create new ListNode with value 0
    greater_head = Create new ListNode with value 0
    
    # Set pointers to the current end of the new lists
    less_ptr = less_head
    greater_ptr = greater_head

    # Traverse the original list
    current_node = head
    While current_node is not null:
        
        # Compare the current node's value with x
        If current_node.value < x:
            # Attach this node to the less list
            less_ptr.next = current_node
            less_ptr = less_ptr.next # move the less pointer
        Else:
            # Attach this node to the greater list
            greater_ptr.next = current_node
            greater_ptr = greater_ptr.next # move the greater pointer
            
        # Move to the next node in the original list
        current_node = current_node.next

    # Set the end of the greater list to null
    greater_ptr.next = null

    # Combine the two lists: 
    # Attach the end of the less list to the start of the greater list
    less_ptr.next = greater_head.next
    
    # Return the start of the new list, skipping the dummy node
    Return less_head.next

Remarks:

Dummy Nodes : The dummy nodes
less_head

and
greater_head

help in easily managing the new lists and are ultimately skipped in the final combined list.
Edge Handling : By setting
greater_ptr.next

to
null

, any leftover links from the original list that might follow
greater_ptr

are cut off.
Preservation of Order : By attaching nodes to
less_ptr

or
greater_ptr

and moving those pointers forward without changing node orders, we preserve the original relative order within each partition.

This detailed explanation, combined with the pseudocode, ensures clarity in understanding the solution strategy and the steps required to solve the partition problem on linked lists effectively.