题目

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

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

示例 1：

img

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

示例 2：

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

提示：

  • 链表中节点的数目在范围 [0, 200] 内
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

实现代码

使用双指针方式，维护两个链表，小于x的一个链表，大于等于x的放一个链表，最后再进行合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode partition(ListNode head, int x) {

    ListNode p = head;
    ListNode pp = new ListNode(-1), p1 = pp;
    ListNode ppp = new ListNode(-1), p2 = ppp;
    while(p != null) {
      if(p.val < x) {
        p1.next = p;
        p1 = p1.next;
      }else{
        p2.next = p;
        p2 = p2.next;
      }
      // 节点每次添加到子链表之后与原链表进行断开
      ListNode temp = p.next;
      p.next = null;
      p = temp;
    }

    // 合并两个子链接
    p1.next = ppp.next;
    return pp.next;
  }
}

代码解释

代码片段一

1
2
3
ListNode temp = p.next;
p.next = null;
p = temp;

当前节点与原链表进行断开，不断开会产生环

假设没有这段代码，那么在两条子链接合并之前如下图：

合并之后：

可见会形成环

为什么会形成环呢？

本质上是因为x的左边存在大于等于x的节点或右边存在小于x的节点，进行合并时就会出现环