2021-01-03 | 86. 分隔链表

Bertha 。 2023-01-01 13:51 109阅读 0赞

### 1. 题目描述 ###

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

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

示例：

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

### 2. 解题思路 ###

对于这道题目，一个很直接的思路就是初始化两个链表，一个链表来存储小于x的值，另一个链表来存储大于x的值。

这里还初始化了两个链表：mallHead 和 largeHead。这两个是链表的哑节点，即它们的 next 指针指向链表的头节点，这样做的目的是为了更方便地处理头节点为空的边界条件。

遍历结束后，将 large 的 next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点，我们需要切断这个引用。同时将 small 的 next 指针指向 largeHead 的 next 指针指向的节点，即真正意义上的 large 链表的头节点。最后返回 smallHead 的 next 指针就是最后的答案。

**复杂度分析：**

*  时间复杂度: O(n)，其中 n 是原链表的长度，因为对该链表进行了一次遍历。
 *  空间复杂度: O(1)。

### 3. 代码实现 ###

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @param {number} x * @return {ListNode} */
    var partition = function(head, x) { 
        let small = new ListNode(0)
        const smallHead = small
        let large = new ListNode(0)
        const largeHead = large
    
        while(head){ 
            if(head.val < x){ 
                small.next = head
                small = small.next
            }else{ 
                large.next = head
                large = large.next
            }
            head = head.next
        }
    
        large.next = null
        small.next = largeHead.next
        return smallHead.next
    };

### 4. 提交结果 ###

![在这里插入图片描述][20210103005846493.png]

[20210103005846493.png]: /images/20221120/20cf17c95b62431d9a454138f10c8a48.png?