分隔链表

Anton原创大约 1 分钟

题目：

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

输入：head = [2,1], x = 2
输出：[1,2]

思考：

提示

利用两个辅助链表，分别保存小于 x 和大于等于 x 的节点
遍历原链表，将其分成两个部分，保存到两个辅助链表中
进行拼接，小链表尾节点指向大链表头节点，大链表尾节点 next 置空，防止成环

题解：

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode big = new ListNode(0);

        ListNode smallTmp = small,bigTmp = big;

        while(head != null){
            if(head.val < x){
                smallTmp.next = head;
                smallTmp = smallTmp.next;
            }else{
                bigTmp.next = head;
                bigTmp = bigTmp.next;
            }
            head = head.next;
        }

        smallTmp.next = big.next;
        bigTmp.next = null;

        return small.next;
    }
}