leetcode如何分隔链表
问题描述
给定一个链表和一个特定值x,要求将链表分隔成两部分,使得所有小于x的节点都位于大于或等于x的节点之前。
解决思路
问题可以通过创建两个新的链表来解决,分别是小于x的链表和大于或等于x的链表。然后遍历原链表,将小于x的节点插入到小于x的链表中,大于或等于x的节点插入到大于或等于x的链表中。最后将小于x的链表的尾节点指向大于或等于x的链表的头节点即可。
代码实现
public ListNode partition(ListNode head, int x) {
ListNode smallerHead = new ListNode(0); // 创建小于x的链表的头节点
ListNode smaller = smallerHead; // 创建临时指针指向小于x的链表
ListNode greaterEqualHead = new ListNode(0); // 创建大于或等于x的链表的头节点
ListNode greaterEqual = greaterEqualHead; // 创建临时指针指向大于或等于x的链表
ListNode current = head; // 创建遍历原链表用的指针
while (current != null) {
if (current.val < x) { // 当前节点小于x时,插入到小于x的链表中
smaller.next = current;
smaller = smaller.next;
} else { // 当前节点大于或等于x时,插入到大于或等于x的链表中
greaterEqual.next = current;
greaterEqual = greaterEqual.next;
}
current = current.next; // 移动指针到下一个节点
}
greaterEqual.next = null; // 大于或等于x的链表的尾节点指向null
smaller.next = greaterEqualHead.next; // 将小于x的链表的尾节点指向大于或等于x的链表的头节点
return smallerHead.next; // 返回小于x的链表的头节点
}
算法分析
假设链表的长度为n。
1. 创建两个临时指针smaller和greaterEqual,所以时间复杂度为O(1)。
2. 遍历原链表,将节点插入到小于x的链表或大于或等于x的链表中,所以时间复杂度为O(n)。
3. 最后将小于x的链表的尾节点指向大于或等于x的链表的头节点,所以时间复杂度为O(1)。
综上所述,该算法的时间复杂度为O(n)。
上一篇
计算机操作系统的功能是什么 猜您想看
-
如何在Linux系统中进行系统备份和容灾
Linux中的...
2023年05月10日 -
如何使用Steam的云存档功能来保存和共享游戏进度记录?
。如何使用St...
2023年05月13日 -
如何在EXSI中创建虚拟磁盘
如何在ESXi...
2023年04月17日 -
Python面向对象的初级知识是什么
1. 什么是面...
2023年05月26日 -
PostgreSQL在启动时怎么分配共享缓存
如何在Post...
2023年07月23日 -
如何在魅族手机上设置断网自动关机
如何在魅族手机...
2023年04月15日