“给定一个链表和特定值,对链表进行分割,使所有小于特定值的节点都出现在特定值节点之前。”
题目链接:
来源:力扣(LeetCode)
链接:86. 分隔链表 - 力扣(LeetCode) (leetcode-cn.com)
给你一个链表的头节点 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]
这道题只需要两个链表,一个链表存放特定值前的节点,一个链表存放特定值后的界面,在遍历完成后,将两个链表链接即可。
具体实现就是,用两个链表分别指向当前链表的尾结点,然后从前往后遍历,根据当前节点是否大于特定值来讲这个节点放入到不同的链表中。
代码参考:
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;
}
}
时间复杂度 : O(n)
其中n是链表的长度。
空间复杂度: O(1)
对链表进行一次遍历,然后根据当前节点是否大于特定值来讲这个节点放入到特定链表下,最后合并链表。