Leetcode Study Day 31

Partition List

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.

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

I saw a short and elegant solution from Leetcode.

Firstly, it initialised two Listnode, than using two pointers to track the nodes that are less than x and the nodes that are greater than or equal to x. If the current value is smaller than x, we link the first node to the current node. Otherwise, we link the second node to the current node. Then, we update the current node to the next node.

Finally, we set the second node’s next node to nullptr and link the first node to the second node’s next node.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode node1(0), node2(0);
        ListNode *p1 = &node1;
        ListNode *p2 = &node2;
        while(head){
            if(head->val<x){
                p1 -> next = head;
                p1 = p1 -> next;
            }
            else{
                p2 -> next = head;
                p2 = p2 -> next;
            }
            head = head -> next;
        }
        p2 -> next = nullptr;
        p1 -> next = node2.next;
        return node1.next;
    }
};