86. Partition List

Question

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.

Solution 1

生成前后两个部分的dummy链表头。
遍历原链表，当当前值小于x时则将当前节点添加到第一个链表头后。
当当前值大于x时则将当前节点添加到第二个链表头后。

遍历完成后将第二个链表头的下一个节点添加到第一个链表的下一个节点上。然后将第二个链表的尾部指向null。

返回第一个dummy链表节点的下一个节点即可。

Code

/**
 * 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 dummy1 = new ListNode(), dummy2 = new ListNode();
        ListNode hd1 = dummy1, hd2 = dummy2;
        while(head != null){
            if(head.val < x){
                dummy1.next = head;
                dummy1 = dummy1.next;
            }
            else{
                dummy2.next = head;
                dummy2 = dummy2.next;
            }
            head = head.next;
        }
        dummy1.next = hd2.next;
        dummy2.next = null;
        
        return hd1.next;
    }
}

Solution 2

遍历整个链表，根据各个节点的值将其保存在两个队列中。

设置一个dummy节点头，将两个队列中的节点按顺序挤出并生成新链表。
返回dummy节点头的下一个节点即可。

Code

/**
 * 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) {
        Queue<ListNode> q1 = new LinkedList<>();
        Queue<ListNode> q2 = new LinkedList<>();
        while(head != null){
            if(head.val < x) q1.add(head);
            else q2.add(head);
            head = head.next;
        }
        
        ListNode dummy = new ListNode();
        ListNode res = dummy;
        
        while(!q1.isEmpty()){
            res.next = q1.poll();
            res = res.next;
        }
        
        while(!q2.isEmpty()){
            res.next = q2.poll();
            res = res.next;
        }
        res.next = null;
        return dummy.next;
    }
}