502，分隔链表的解决方式

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

It’s when you start to become really afraid of death that you learn to appreciate life.

只有当你真正感受到对死亡的恐惧，你才会学到要珍惜生命。

问题描述

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

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

示例：

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

四指针解决

在算法中双指针我们经常听过，但四指针还是比较少的，四指针顾名思义就是使用4个指针来解决。

这题是让把节点值小于x的节点都放到前面，最简单的一种解决方式就是把原链表的节点分隔为两个链表，其中一个链表节点的值都是小于x的，另一个链表节点的值都是大于或等于x的，最后再把这两个链表合并即可。这里要使用四个指针，其中两个指向小的链表，两个指向大的链表，原理如下图所示

最后我们再来看下代码

 1public ListNode partition(ListNode head, int x) {
 2    //小链表的头
 3    ListNode smallHead = new ListNode(0);
 4    //大链表的头
 5    ListNode bigHead = new ListNode(0);
 6    //小链表的尾
 7    ListNode smallTail = smallHead;
 8    //大链表的尾
 9    ListNode bigTail = bigHead;
10    //遍历head链表
11    while (head != null) {
12        if (head.val < x) {
13            //如果当前节点的值小于x，则把当前节点挂到小链表的后面
14            smallTail = smallTail.next = head;
15        } else {//否则挂到大链表的后面
16            bigTail = bigTail.next = head;
17        }
18
19        //继续循环下一个结点
20        head = head.next;
21    }
22    //最后再把大小链表拼接在一块即可。
23    smallTail.next = bigHead.next;
24    bigTail.next = null;
25    return smallHead.next;
26}