Partition List Algorithm

The Partition List Algorithm is a computer algorithm used in sorting and organizing data structures, particularly linked lists. It is commonly employed as part of the quicksort algorithm or other divide and conquer techniques. The main objective of the partition list algorithm is to take a specific value or node as the pivot, and reorder the list in such a way that all the nodes less than the pivot come before it, and all the nodes greater than the pivot come after it. This helps in simplifying the problem and allows for efficient sorting and searching of data within the list, making it easier for further processing. The algorithm works by iterating through the linked list and comparing the values of each node with the pivot value. In case the current node's value is less than the pivot, the algorithm moves it to the left or before the pivot, and if the value is greater than the pivot, it leaves the node or moves it to the right or after the pivot. This process is repeated until all the nodes have been processed, resulting in a partitioned list. The partition list algorithm can be implemented using both recursive and iterative methods, depending on the specific use case and requirements. This algorithm is highly versatile and can be adapted for different data structures and programming languages, making it a fundamental tool in computer science and software engineering.
/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        ListNode less_than_head(0);
        ListNode no_less_than_head(0);
        ListNode *less_than = &less_than_head;
        ListNode *no_less_than = &no_less_than_head;
        
        ListNode *node = head;
        while (node != NULL) {
            if (node->val < x) {
                less_than->next = node;
                node = node->next;
                less_than = less_than->next;
            }
            else {
                no_less_than->next = node;
                node = node->next;
                no_less_than = no_less_than->next;
            }
        }
        no_less_than->next = NULL;
        less_than->next = no_less_than_head.next;
        return less_than_head.next;
    }
};

LANGUAGE:

DARK MODE: