leetcode链表之分割链表的示例分析
问题描述:
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
示例:
输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
解题思路:
为了解决这个问题,我们可以创建两个链表,分别用于保存小于x的节点和大于等于x的节点,最后再将这两个链表合并即可。
1. 创建两个哑节点dummy1和dummy2,分别作为两个链表的头节点。
2. 遍历原链表,将小于x的节点连接到dummy1链表的尾部,将大于等于x的节点连接到dummy2链表的尾部。
3. 最后将dummy1链表的尾节点指向dummy2链表的头节点,形成最终的链表。
代码实现:
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0); // 小于x的链表的哑节点
ListNode dummy2 = new ListNode(0); // 大于等于x的链表的哑节点
ListNode curr1 = dummy1; // 当前小于x的链表的尾节点
ListNode curr2 = dummy2; // 当前大于等于x的链表的尾节点
while (head != null) {
if (head.val < x) {
curr1.next = head;
curr1 = curr1.next;
} else {
curr2.next = head;
curr2 = curr2.next;
}
head = head.next;
}
// 将两个链表连接起来
curr2.next = null;
curr1.next = dummy2.next;
return dummy1.next;
}
复杂度分析:
时间复杂度:遍历原链表的时间复杂度为O(n),其中n为链表节点的个数。
空间复杂度:创建了两个新的链表,因此空间复杂度为O(1)。
上一篇
消息中间件的四大MQ如何比较 猜您想看
-
Node中怎么处理HTTP请求
Node.js...
2023年05月26日 -
VisualStudio中类库引用类库失败的问题该怎么解决
一、检查引用类...
2023年05月25日 -
C++中的T*返回值有什么作用
什么是T*返回...
2023年05月22日 -
如何在Windows系统中使用远程桌面连接其他电脑
Windows...
2023年05月12日 -
SQL Server怎么将已分区表转换成普通表
一、概述SQL...
2023年05月26日 -
如何深入了解Java虚拟机内存
一、Java ...
2023年05月23日