Leecode之分割链表

一枕眠秋雨

发布于 2024-03-11 17:57:29

1100

发布于 2024-03-11 17:57:29

文章被收录于专栏：司钰秘籍

一.题目及剖析

https://leetcode.cn/problems/partition-list-lcci/description/

给你一个链表的头节点 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为分界线进行分堆,最后再将两链表合并

三.代码引入

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)
    return head;
    struct ListNode *lessHead, *lessTail, *greaterHead, *greaterTail, *pcur;
    lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    pcur = head;
    while(pcur)
    {
        if(pcur->val < x)
        {
            lessTail->next = pcur;
            lessTail = lessTail->next;
        }
        else
        {
            greaterTail->next = pcur;
            greaterTail = greaterTail->next;
        }
        pcur = pcur->next;
    }
    greaterTail->next = NULL;
    lessTail->next = greaterHead->next;
    return lessHead->next;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-02-18，如有侵权请联系 cloudcommunity@tencent.com 删除

list