一、题目
给你一个链表的头节点 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]文章来源:https://www.toymoban.com/news/detail-681541.html
二、C# 题解
最初打算在原链表上改,想了很久发现难以操作,需要引入队列。最后决定,不如直接新建两个链表 small
和 large
,分别用于添加节点值
<
x
< x
<x 和节点值
≥
x
\geq x
≥x 的节点。
遍历链表 head
后,拼接 small
和 large
链表,最终返回头节点 small.next
即可。文章来源地址https://www.toymoban.com/news/detail-681541.html
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode Partition(ListNode head, int x) {
ListNode small = new ListNode(0), large = new ListNode(0);
ListNode p = small, q = large; // p 指向 small 尾端,q 指向 large 尾端
while (head != null) { // 遍历原链表
if (head.val < x) { // 小值放入 small 链表中
p.next = head;
p = p.next;
}
else {
q.next = head; // 大值放入 large 链表中
q = q.next;
}
head = head.next;
}
p.next = large.next; // 连接两个链表
q.next = null; // 断后
return small.next;
}
}
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( n ) O(n) O(n)。
到了这里,关于LeetCode 面试题 02.04. 分割链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!