网站运营维护,百度推广 做网站,WordPress pwa,自助建站编辑器文章目录 一、题目二、C# 题解 一、题目 给你一个链表的头节点 head 和一个特定值 x#xff0c;请你对链表进行分隔#xff0c;使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。 点击此处跳转题目。
示例 1#… 文章目录 一、题目二、C# 题解 一、题目 给你一个链表的头节点 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] 二、C# 题解 最初打算在原链表上改想了很久发现难以操作需要引入队列。最后决定不如直接新建两个链表 small 和 large分别用于添加节点值 x x x 和节点值 ≥ x \geq x ≥x 的节点。 遍历链表 head 后拼接 small 和 large 链表最终返回头节点 small.next 即可。
/*** 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)。
