Leecode之分割链表
一.题目及剖析
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 删除
评论
登录后参与评论
推荐阅读
目录