算法日记-LeetCode-86.分隔链表

2023-08-15

字数统计: 320字 | 阅读时长≈ 1分

算法日记-LeetCode-86.分隔链表

题目大意

给一个链表list以及一个值x，将所有小于x的节点移到链表前面，不改变其原有的顺序

如：

x = 3

graph LR
A((1)) --> B((4)) --> C((3)) --> D((2)) --> E((2)) --> F((3)) --> G((5))
H((1)) --> I((2)) --> J((2)) --> K((4)) --> L((3)) --> M((3)) --> N((5))

解题思路

这个有点类似排序中的快排，给定一个标准值，大于标准值的往前，小于标准值的往后。在链表中没有索引，不能像数组中方便的交换两个值。

题目要求不能改变相对顺序，我们可以按照题目说的分隔，将大于等于x和小于x的分别存放到两个链表less和more中，最后将less的最后一个节点的next指向more的第一个节点即可。

注意：头节点是空节点，应该返回它的next，即less.next;

代码

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return head;
        ListNode less = new ListNode();
        ListNode more = new ListNode();
        ListNode p = less, q = more;
        while (head != null) {
            if (head.val >= x) {
                q.next = head;
                q = q.next;
            } else {
                p.next = head;
                p = p.next;
            }
            head = head.next;
        }
        p.next = more.next;
        q.next = null;
        return less.next;
    }
}

本文作者： Naskete
本文链接： https://Naskete.github.io/2023/08/15/algorithm/算法日记-LeetCode-86.分隔链表/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！