86. 分隔链表
难度中等455 收藏 分享 切换为英文 接收动态 反馈
给你一个链表的头节点 head
和一个特定值x
,请你对链表进行分隔,使得所有 小于 x
的节点都出现在 大于或等于 x
的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:
image<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--dsw-fill-tertiary-rgba)); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
</pre>
示例 2:
<pre style="box-sizing: border-box; font-size: 13px; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; margin-top: 0px; margin-bottom: 1em; overflow: auto; background: rgba(var(--dsw-fill-tertiary-rgba)); padding: 10px 15px; color: rgba(var(--grey-9-rgb),1); line-height: 1.6; border-radius: 3px; white-space: pre-wrap;">输入:head = [2,1], x = 2
输出:[1,2]
</pre>
提示:
- 链表中节点的数目在范围
[0, 200]
内 -100 <= Node.val <= 100
-200 <= x <= 200
思路:
创建左右两个虚拟头节点,遍历源链表,>=x的,添加到右边,<x的添加到左边
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode lhead = new ListNode(0);
ListNode lTail = lhead;
ListNode rhead = new ListNode(0);
ListNode rTail = rhead;
while(head !=null){
if(head.val < x){
lTail.next = head;
lTail = head;
}else{
rTail.next = head;
rTail = head;
}
head = head.next;
}
rTail.next = null;
lTail.next = rhead.next;
return lhead.next;
}
}
网友评论