关键词：双链表

1. 题目描述

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

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

示例：

  1. 输入：head = 1->4->3->2->5->2, x = 3
  2. 输出：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. 代码实现

    1. /**
    2. * Definition for singly-linked list.
    3. * function ListNode(val) {
    4. *     this.val = val;
    5. *     this.next = null;
    6. * }
    7. */
    8. /**
    9. * @param {ListNode} head
    10. * @param {number} x
    11. * @return {ListNode}
    12. */
    13. var partition = function(head, x) {
    14.   let small = new ListNode(0)
    15.   const smallHead = small
    16.   let large = new ListNode(0)
    17.   const largeHead = large
    19.   while(head){
    20.       if(head.val < x){
    21.           small.next = head
    22.           small = small.next
    23.       }else{
    24.           large.next = head
    25.           large = large.next
    26.       }
    27.       head = head.next
    28.   }
    30.   large.next = null
    31.   small.next = largeHead.next
    32.   return smallHead.next
    33. };

    4. 提交结果

    image.png