题目
编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。
分割元素 x 只需
处于“右半部分”即可,其不需要被置于左右两部分之间。
https://leetcode-cn.com/problems/partition-list-lcci/
示例:
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8
Related Topics 链表 双指针
👍 21 👎 0
分析及反思
双指针法,思路类似于“荷兰国旗🇳🇱”的颜色排序题目.
p指针左边必定是小于x的节点,q指针遍历链表,遇到val<x时,交换p,q的val,并且p=p.next
其中不需要保持原有的顺序
,86
题需要。所以有所异同。
https://leetcode-cn.com/problems/partition-list/
代码
该题 不需要保持原有顺序
info
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.3 MB,击败了100.00% 的Java用户
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode p, q;
p = q = head;
while (q != null) {
if (q.val < x) {//肯定是大于等于的交换
int t = q.val;
q.val = p.val;
p.val = t;
p = p.next;
}
q = q.next;
}
return head;
}
}
86题 保持后者的大小相对顺序
11:06 info
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.2 MB,击败了5.55% 的Java用户
class Solution {
public ListNode partition(ListNode head, int x) {
//维护两条链表,利用尾插法保证相对顺序不变
ListNode min = new ListNode(-1);
ListNode max = new ListNode(-1);
ListNode p = head, p1 = min, p2 = max;//mark 链表的头。
while (p != null) {
if (p.val < x) {
min.next = p;
min = min.next;
} else {
max.next = p;
max = max.next;
}
p = p.next;
}
min.next = p2.next;//小的尾巴指向大的头部 尾插法
max.next = null;///对于非空表,将尾结点指针域置空 否则 Error - Found cycle in the ListNode
return p1.next;
}
}
本文地址:https://dxoca.cn/Algorithm/372.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。