02.04 分割链表

1、题目

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

你不需要 保留 每个分区中各节点的初始相对位置。

1）示例1

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

2）示例2

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

2、初步作答

2.1 思路

• 分隔链表相当于把一个链表分成两个链表，一个链表值都比x大，一个链表值都比x小
• 再连接两个链表

2.2 做法

• 新建两个空的表头节点，用以存放两个链表
• 判断值与x的大小关系，形成两个链表
• 连接链表形成新的链表，返回链表的表头节点

2.3 代码

public ListNode partition(ListNode head, int x) {
    ListNode a = new ListNode(0);
    ListNode b = new ListNode(0);
    ListNode ahead = a;
    ListNode bhead = b;
    while (head!=null){
        if(head.val < x){
            //a.val = head.val;
            a.next = head;
            a = a.next;
        }else{
            //b.val = head.val;
            b.next = head;
            b = b.next;
        }
        head = head.next;
    }
    b.next = null;
    a.next = bhead.next;
    return ahead.next;
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.1 MB, 在所有 Java 提交中击败了5.75%的用户
通过测试用例：166 / 166

2.4 思考

链表的表头节点需要使用new关键字申请内存空间，不能直接使用ListNode a = head,b = head新建表头节点，因为这样新建的表头空间指向的内存空间还是head的内存空间，不能得到两个新的链表。

3、其余解法

• 来自力扣作者exciting-hellmanjlb

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode prev = head, curr = head.next;
        while (curr != null) {
            if (curr.val < x) {
                prev.next = curr.next;
                curr.next = head;
                head = curr;
                curr = prev.next;
            } else {
                curr = curr.next;
                prev = prev.next;
            }
        }
        return head;
    }
}