86. 分隔链表:
给你一个链表的头节点 head
和一个特定值 x
,请你对链表进行分隔,使得所有 小于 x
的节点都出现在 大于或等于 x
的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
样例 1:
文章来源:https://www.toymoban.com/news/detail-714793.html
输入:
head = [1,4,3,2,5,2], x = 3
输出:
[1,2,2,4,3,5]
样例 2:
输入:
head = [2,1], x = 2
输出:
[1,2]
提示:
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200
分析:
- 面对这道算法题目,二当家的再次陷入了沉思。
- 直接模拟即可,题目没有特别说明对空间复杂度的要求,所以我们直接新建两个虚拟节点分别作为小于
x
和大于或等于x
的链表头节点,分别对小于x
的节点和大于或等于x
的节点拉链表,遍历完毕后,将两个新建的链表结构再连接起来即可。 - 新建两个节点是为了让代码结构简单,少一些判断逻辑,可以考虑一下如果不新建两个虚拟节点是否也可以完成,不过考虑考虑就好了,那样得不偿失。
- rust处理链表相比其他语言要严肃一点,没那么自由,不过习惯就好了。
题解:
rust:
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn partition(mut head: Option<Box<ListNode>>, x: i32) -> Option<Box<ListNode>> {
let (mut small_head, mut large_head) = (ListNode::new(0), ListNode::new(0));
let (mut small, mut large) = (&mut small_head, &mut large_head);
while let Some(mut node) = head {
head = node.next.take();
if node.val < x {
small.next = Some(node);
small = small.next.as_mut().unwrap();
} else {
large.next = Some(node);
large = large.next.as_mut().unwrap();
}
}
small.next = large_head.next;
return small_head.next;
}
}
go:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
smallHead, largeHead := &ListNode{}, &ListNode{}
small, large := smallHead, largeHead
for head != nil {
if head.Val < x {
small.Next = head
small = small.Next
} else {
large.Next = head
large = large.Next
}
head = head.Next
}
large.Next = nil
small.Next = largeHead.Next
return smallHead.Next
}
c++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *smallHead = new ListNode(0);
ListNode *small = smallHead;
ListNode *largeHead = new ListNode(0);
ListNode *large = largeHead;
while (head != nullptr) {
if (head->val < x) {
small->next = head;
small = small->next;
} else {
large->next = head;
large = large->next;
}
head = head->next;
}
large->next = nullptr;
small->next = largeHead->next;
return smallHead->next;
}
};
python:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
small_head, large_head = ListNode(0), ListNode(0)
small, large = small_head, large_head
while head:
if head.val < x:
small.next = head
small = small.next
else:
large.next = head
large = large.next
head = head.next
large.next = None
small.next = large_head.next
return small_head.next
java:
/**
* 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 smallHead = new ListNode(0);
ListNode small = smallHead;
ListNode largeHead = new ListNode(0);
ListNode large = largeHead;
while (head != null) {
if (head.val < x) {
small.next = head;
small = small.next;
} else {
large.next = head;
large = large.next;
}
head = head.next;
}
large.next = null;
small.next = largeHead.next;
return smallHead.next;
}
}
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~文章来源地址https://www.toymoban.com/news/detail-714793.html
到了这里,关于算法leetcode|86. 分隔链表(rust重拳出击)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!