02.04. Partition List

Description

Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions.

Example:


Input: head = 3->5->8->5->10->2->1, x = 5

Output: 3->1->2->10->5->5->8

Solutions

Solution 1: Concatenating Lists

We create two lists, left and right, to store nodes that are less than x and nodes that are greater than or equal to x, respectively.

Then we use two pointers p1 and p2 to point to the last node of left and right respectively, initially both p1 and p2 point to a dummy head node.

Next, we traverse the list head. If the value of the current node is less than x, we add the current node to the end of the left list, i.e., p1.next = head, and then set p1 = p1.next; otherwise, we add the current node to the end of the right list, i.e., p2.next = head, and then set p2 = p2.next.

After the traversal, we point the tail node of the left list to the first valid node of the right list, i.e., p1.next = right.next, and then point the tail node of the right list to a null node, i.e., p2.next = null.

Finally, we return the first valid node of the left list.

The time complexity is $O(n)$, where $n$ is the length of the list. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptSwift

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        left, right = ListNode(0), ListNode(0)
        p1, p2 = left, right
        while head:
            if head.val < x:
                p1.next = head
                p1 = p1.next
            else:
                p2.next = head
                p2 = p2.next
            head = head.next
        p1.next = right.next
        p2.next = None
        return left.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        ListNode p1 = left;
        ListNode p2 = right;
        for (; head != null; head = head.next) {
            if (head.val < x) {
                p1.next = head;
                p1 = p1.next;
            } else {
                p2.next = head;
                p2 = p2.next;
            }
        }
        p1.next = right.next;
        p2.next = null;
        return left.next;
    }
}

/**
 * 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* left = new ListNode(0);
        ListNode* right = new ListNode(0);
        ListNode* p1 = left;
        ListNode* p2 = right;
        for (; head; head = head->next) {
            if (head->val < x) {
                p1->next = head;
                p1 = p1->next;
            } else {
                p2->next = head;
                p2 = p2->next;
            }
        }
        p1->next = right->next;
        p2->next = nullptr;
        return left->next;
    }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    left, right := &ListNode{}, &ListNode{}
    p1, p2 := left, right
    for ; head != nil; head = head.Next {
        if head.Val < x {
            p1.Next = head
            p1 = p1.Next
        } else {
            p2.Next = head
            p2 = p2.Next
        }
    }
    p1.Next = right.Next
    p2.Next = nil
    return left.Next
}

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

function partition(head: ListNode | null, x: number): ListNode | null {
    const [left, right] = [new ListNode(), new ListNode()];
    let [p1, p2] = [left, right];
    for (; head; head = head.next) {
        if (head.val < x) {
            p1.next = head;
            p1 = p1.next;
        } else {
            p2.next = head;
            p2 = p2.next;
        }
    }
    p1.next = right.next;
    p2.next = null;
    return left.next;
}

/** public class ListNode {
*    var val: Int
*    var next: ListNode?
*    init(_ x: Int) {
*        self.val = x
*        self.next = nil
*    }
* }
*/

class Solution {
    func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
        let leftDummy = ListNode(0)
        let rightDummy = ListNode(0)
        var left = leftDummy
        var right = rightDummy
        var head = head

        while let current = head {
            if current.val < x {
                left.next = current
                left = left.next!
            } else {
                right.next = current
                right = right.next!
            }
            head = head?.next
        }

        right.next = nil
        left.next = rightDummy.next

        return leftDummy.next
    }
}

02.04. Partition List

Description

Solutions

Solution 1: Concatenating Lists

Comments