Partition List

class Solution {
public:
    ListNode* separate(ListNode* node, int pivot) {
        ListNode* less_head = new ListNode(0);
        ListNode* less_tail = less_head;
        ListNode* greater_head = new ListNode(0);
        ListNode* greater_tail = greater_head;
        while (node != NULL) {
            if (node->val < pivot) {
                less_tail->next = node;
                less_tail = less_tail->next;
            } else {
                greater_tail->next = node;
                greater_tail = greater_tail->next;
            }
            node = node->next;
        }
        greater_tail->next = NULL;
        less_tail->next = greater_head->next;
        return less_head->next;
    }
};

The provided C++ solution defines a method named separate inside a Solution class, which aims to partition a linked list around a given pivot value. The method accepts a pointer to the head of the list (ListNode* node) and an integer (pivot) representing the pivot value. The list nodes with values less than the pivot are moved to one linked list, and those with values greater or equal are moved to another.

To achieve this partition:

• Initialize two dummy head nodes, less_head and greater_head, to simplify node connection without handling special cases for the head node.
• Use two pointers, less_tail and greater_tail, to maintain the ends of the two growing lists (less than pivot and greater/equal to pivot).

During iteration through the input list:

• Nodes with values less than the pivot are appended to the list headed by less_head.
• Nodes with values greater or equal to the pivot are appended to the list headed by greater_head.
• At the end of the iteration, ensure the list headed by greater_tail is properly terminated with a NULL to signify the end of the list.

Finally:

• Connect the list containing nodes less than the pivot to the list of nodes greater than or equal to the pivot.
• Return the head of the modified list, which effectively omits the initial dummy node (less_head->next).

This method efficiently partitions the linked list in one pass, using constant space for pointers and ensuring that nodes are rearranged without creating new ones, just re-linking the existing nodes according to their values relative to the pivot.

class Solution {
    public ListNode split(ListNode start, int pivot) {
        ListNode lowHead = new ListNode(0);
        ListNode lowTail = lowHead;
        ListNode highHead = new ListNode(0);
        ListNode highTail = highHead;
    
        while (start != null) {
            if (start.val < pivot) {
                lowTail.next = start;
                lowTail = lowTail.next;
            } else {
                highTail.next = start;
                highTail = highTail.next;
            }
    
            start = start.next;
        }
    
        highTail.next = null;
        lowTail.next = highHead.next;
        return lowHead.next;
    }
}

This Java solution addresses the problem of partitioning a linked list around a given pivot value, such that all nodes less than the pivot come before all nodes greater than or equal to the pivot. The function split is defined to handle this logic and takes two parameters: the head of the list (start) and the pivot value (pivot).

Here's how the solution operates:

1. Two dummy nodes, lowHead and highHead, are created to form the beginning of two separate linked lists: one for values lower than the pivot and another for values higher or equal.
2. Two pointers, lowTail and highTail, start at these dummy nodes and help in building the two lists.
3. As you iterate through the original list, each node is either added to the end of the lowTail list (if its value is less than the pivot) or to the highTail list (if its value is greater than or equal).
4. This iteration continues until all elements of the original list are examined.
5. The list of higher or equal values must have its last node pointing to null to denote the end of the list.
6. To merge the two lists, set the next pointer of the lowTail (end of lower value list) to the head of the higher values list, which starts right after the dummy node highHead.
7. Finally, return the head of the modified list, which is now properly partitioned, by pointing to the next of lowHead.

This method effectively re-arranges the nodes of the original list without needing additional memory for new nodes, thereby providing an efficient in-place solution.

struct ListNode* separate(struct ListNode* start, int threshold) {
    struct ListNode* less_than_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    less_than_head->next = NULL;
    struct ListNode* less = less_than_head;
    struct ListNode* greater_than_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    greater_than_head->next = NULL;
    struct ListNode* greater = greater_than_head;
        
    while (start != NULL) {
        if (start->val < threshold) {
            less->next = start;
            less = less->next;
        } else {
            greater->next = start;
            greater = greater->next;
        }
        start = start->next;
    }
    greater->next = NULL;
    less->next = greater_than_head->next;
    return less_than_head->next;
}

The given C language code defines a function separate that partitions a linked list based on a threshold value. The function accepts a linked list (start) and an integer (threshold) as parameters. The goal is to rearrange the linked list so that all nodes with values less than the threshold are moved before nodes with values equal to or greater than the threshold.

• The function initializes two dummy head nodes: less_than_head for the list of elements less than the threshold and greater_than_head for the list of elements equal to or greater than the threshold.
• It iterates through the input list, and segregates nodes into the less and greater lists based on their values compared to the threshold.
• After the iteration, ensure that the last node in the greater list points to NULL to mark the end of that list.
• The next of the last less node points to the first element of the greater_than_head list to concatenate the two lists.
• Finally, return the next of the less_than_head which is effectively the head of the newly arranged linked list.

This rearrangement is done in-place, and the algorithm efficiently partitions the nodes with a single traversal through the original list. The approach ensures that the relative order of nodes in each partition is preserved and it uses constant space for the pointers, excluding the input list nodes themselves.

var splitList = function (node, pivot) {
    var lowStart = new ListNode(0);
    var lowEnd = lowStart;
    var highStart = new ListNode(0);
    var highEnd = highStart;
    while (node != null) {
        if (node.val < pivot) {
            lowEnd.next = node;
            lowEnd = lowEnd.next;
        } else {
            highEnd.next = node;
            highEnd = highEnd.next;
        }
        node = node.next;
    }
    highEnd.next = null;
    lowEnd.next = highStart.next;
    return lowStart.next;
};

The JavaScript function "splitList" is designed to partition a linked list around a pivot value. It rearranges the list so that all nodes with values less than the pivot come before nodes with values greater than or equal to the pivot. Here's a breakdown of how it accomplishes this:

• Initialize two dummy nodes, lowStart and highStart, which act as the starting points for the two parts of the split list.
• Utilize two pointers, lowEnd and highEnd, which help in appending nodes to the respective parts.
• Traverse through the linked list using a while loop. During each iteration, compare the current node's value with the pivot:
  • If the node's value is less than the pivot, append it to the lowEnd.
  • Otherwise, append it to the highEnd.
• After exiting the loop, set the next pointer of highEnd to null to mark the end of the high part of the list.
• Connect the end of the low part list to the beginning of the high part list.
• Return the next node of lowStart as it points to the head of the newly arranged list.

This method effectively partitions the list with a time complexity of O(n) and does not require additional space beyond the few temporary pointers, making it space efficient.

class Solution(object):
    def rearrangeNodes(self, start: ListNode, pivot: int) -> ListNode:
        # Initialize two list heads and current pointers
        lower = lower_head = ListNode(0)
        higher = higher_head = ListNode(0)
    
        while start:
            # Distribute nodes into lower or higher based on their value
            if start.val < pivot:
                lower.next = start
                lower = lower.next
            else:
                higher.next = start
                higher = higher.next
    
            # Proceed to next node in original list
            start = start.next
    
        # Terminate the higher value list
        higher.next = None
        # Connect lower values list to higher values list
        lower.next = higher_head.next
    
        return lower_head.next

The provided Python code defines a function that partitions a linked list around a given pivot value. Each node in the linked list has a numeric value, and the function rearranges the nodes such that all nodes with values less than the pivot are moved before nodes with values greater than or equal to the pivot. The rearrangement is performed using the following steps:

• Initialize two dummy head nodes, lower_head and higher_head, to help in segregating nodes into two lists: one for values lower than the pivot and one for values higher or equal.
• Traverse through the original list. Depending on whether the node's value is less than the pivot, append it to the end of the lower list, or otherwise to the higher list.
• Properly manage the next pointers. After evaluating a node, proceed to the next node in the list.
• Ensure that the higher list is terminated properly to avoid any potential cyclic linking in the list.
• Connect the lower list to the higher list by setting the next pointer of the last node of the lower list to the first node of the higher list.
• Return the next node of lower_head as the new head of the rearranged list, excluding the dummy head.

This solution efficiently partitions the list with a single traversal, resulting in a time complexity of O(n), where n is the number of nodes in the list, and it uses O(1) extra space since no additional nodes are created, only pointers are reassigned.