☆打卡算法☆LeetCode 86、分隔链表 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个链表和特定值，对链表进行分割，使所有小于特定值的节点都出现在特定值节点之前。”

题目链接：

来源：力扣（LeetCode）

链接：86. 分隔链表 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

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

二、解题

1、思路分析

这道题只需要两个链表，一个链表存放特定值前的节点，一个链表存放特定值后的界面，在遍历完成后，将两个链表链接即可。

具体实现就是，用两个链表分别指向当前链表的尾结点，然后从前往后遍历，根据当前节点是否大于特定值来讲这个节点放入到不同的链表中。

2、代码实现

代码参考：

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        while (head != null) {
            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;
    }
}

3、时间复杂度

时间复杂度 ： O(n)

其中n是链表的长度。

空间复杂度： O(1)

三、总结

对链表进行一次遍历，然后根据当前节点是否大于特定值来讲这个节点放入到特定链表下，最后合并链表。