Question

Given 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:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Thinking:

  • Method 1:
    • 分别创建两个链表头用于挂载结点。
    • 记得要将最后的一个位置的next设置为null，不然就可能无限复制下去。
/**
 * 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 dummySmall = new ListNode(0);
        ListNode curSmall = dummySmall;
        ListNode dummyOther = new ListNode(0);
        ListNode curOther = dummyOther;
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                curSmall.next = cur;
                curSmall = curSmall.next;
            }else{
                curOther.next = cur;
                curOther = curOther.next;
            }
            cur = cur.next;
        }
        curOther.next = null;
        curSmall.next = dummyOther.next;
        return dummySmall.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 dummy = new ListNode(0);
        ListNode curDummy = dummy;
        ListNode dummyOther = new ListNode(0);
        ListNode curOther = dummyOther;
        dummy.next = head;
        ListNode cur = dummy.next;
        while(cur != null){
            if(cur.val < x){
                curDummy.next = cur;
                curDummy = curDummy.next;
            }else{
                curOther.next = cur;
                curOther = curOther.next;
            }
            cur = cur.next;
        }
        curOther.next = null;
        curDummy.next = dummyOther.next;
        return dummy.next;
    }
}