算法leetcode｜86. 分隔链表（rust重拳出击）

文章目录

86. 分隔链表：

给你一个链表的头节点

head

和一个特定值

x

，请你对链表进行分隔，使得所有 小于

x

的节点都出现在 大于或等于

x

的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

样例 1：

输入：
    
    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//     }//   }// }implSolution{pubfnpartition(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);whileletSome(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
 * }
 */funcpartition(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) {}
 * };
 */classSolution{public:
    ListNode*partition(ListNode* head,int x){
        ListNode *smallHead =newListNode(0);
        ListNode *small = smallHead;
        ListNode *largeHead =newListNode(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 = nextclassSolution:defpartition(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.nextelse:
                large.next= head
                large = large.next
            head = head.next
        large.next=None
        small.next= large_head.nextreturn 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; }
 * }
 */classSolution{publicListNodepartition(ListNode head,int x){ListNode smallHead =newListNode(0);ListNode small     = smallHead;ListNode largeHead =newListNode(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/ 博客原创~