题目

https://leetcode-cn.com/problems/partition-list/

解法

直观想法是使用两个哑节点，按顺序遍历输入的链表将小于x与大于x的节点分别添加在两个哑节点尾部，最后将两个哑节点所在的链表组合起来。

/**
 * 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 dummy2 = new ListNode(0);
        ListNode dhead = dummy;
        ListNode dhead2 = dummy2;
        ListNode phead = head;
        while (phead != null) {
            if (phead.val < x) {
                dhead.next = new ListNode(phead.val);
                dhead = dhead.next;
            } else {
                dhead2.next = new ListNode(phead.val);
                dhead2 = dhead2.next;
            }
            phead = phead.next;
        }
        dhead.next = dummy2.next;
        return dummy.next;
    }
}

优化

上面的方法new了新节点，其实可以不用new，但要注意最后需要将顺序存储大于等于x节点的链表最后要断开。

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy =  new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode dhead = dummy;
        ListNode dhead2 = dummy2;
        ListNode phead = head;
        while (phead != null) {
            if (phead.val < x) {
                dhead.next = phead;
                dhead = dhead.next;
            } else {
                dhead2.next = phead;
                dhead2 = dhead2.next;
            }
            phead = phead.next;
        }
        dhead2.next = null;
        dhead.next = dummy2.next;
        return dummy.next;
    }
}