86. 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]

解題思路

Use two ListNode, less and greater, to hold nodes with values less than x and which node greater than or equal to x.
Linking two ListNode togother, attach the greater to the end of the less.

Solution

// Definition for singly-linked list.
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode less = new ListNode(0);
        ListNode lessTail = less;
        ListNode greater = new ListNode(0);
        ListNode greaterTail = greater;
        
        while (head != null) {
            if (head.val < x) {
                lessTail.next = new ListNode(head.val);
                lessTail = lessTail.next;
            } else {
                greaterTail.next = new ListNode(head.val);
                greaterTail = greaterTail.next;
            }
            head = head.next;
        }

        lessTail.next = greater.next;
        return less.next;
    }
}

單字

preserve 保存 v.

to keep something as it is, especially in order to prevent it from decaying or being damaged or destroyed

to preserve the environment
We want to preserve the character of the town while improving the facilities.