leetcode链表之分割链表的示例分析

问题描述：

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

示例：

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

解题思路：

为了解决这个问题，我们可以创建两个链表，分别用于保存小于x的节点和大于等于x的节点，最后再将这两个链表合并即可。

1. 创建两个哑节点dummy1和dummy2，分别作为两个链表的头节点。

2. 遍历原链表，将小于x的节点连接到dummy1链表的尾部，将大于等于x的节点连接到dummy2链表的尾部。

3. 最后将dummy1链表的尾节点指向dummy2链表的头节点，形成最终的链表。

代码实现：

public ListNode partition(ListNode head, int x) {
    ListNode dummy1 = new ListNode(0); // 小于x的链表的哑节点
    ListNode dummy2 = new ListNode(0); // 大于等于x的链表的哑节点
    ListNode curr1 = dummy1; // 当前小于x的链表的尾节点
    ListNode curr2 = dummy2; // 当前大于等于x的链表的尾节点
    
    while (head != null) {
        if (head.val < x) {
            curr1.next = head;
            curr1 = curr1.next;
        } else {
            curr2.next = head;
            curr2 = curr2.next;
        }
        head = head.next;
    }
    
    // 将两个链表连接起来
    curr2.next = null;
    curr1.next = dummy2.next;
    
    return dummy1.next;
}

复杂度分析：

时间复杂度：遍历原链表的时间复杂度为O(n)，其中n为链表节点的个数。

空间复杂度：创建了两个新的链表，因此空间复杂度为O(1)。