LeetCode每日一练 —— CM11 链表分割

导读:本篇文章讲解 LeetCode每日一练 —— CM11 链表分割,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

🌟 前言

Wassup guys!我是Edison 😎

今天是 牛客 上的 nowcoder CM11 链表分割

Let’s get it!

在这里插入图片描述



1. 题目分析

现有一链表的头指针 ListNode* pHead,给一定值 x
 
编写一段代码将所有小于 x 的结点排在其余结点之前,且不能改变原来的数据顺序;
 
返回重新排列后的链表的头指针。

示例一

输入:[3,5,1,6,3,4],x = 4
 
输出:[3,1,3,5,6,4]。
 
注意:x 等于 4,那么比 x 小的就是:313,所以这三个数要排在前面,顺序不能变;
 
那么比 x 大的就是:56,所以这两个数要排在 3,1,3 的后面,顺序不能变;
 
再把 x 放在最后

2. 题目图解

这道题的解题思路为:

(1)遍历原链表;
 
(2)把 小于 x 的插入到一个新的链表 1
 
(3)把 大于等于 x 的插入到一个新的链表 2
 
(4)然后把 链表 1链表 2 链接起来;

定义 cur 指向原链表的头节点,用来遍历原链表;

定义 链表 1lessHeadlessTail 都指向 哨兵位 的节点(不为 NULL);

定义 链表 2greaterHeadgreaterTail 都指向 哨兵位 的节点(不为 NULL);
在这里插入图片描述

动图一👇
在这里插入图片描述

动图二👇
在这里插入图片描述

动图三👇
在这里插入图片描述

链表 1链表 2 链接起来
在这里插入图片描述
注意:

题目是没有说链表是带 哨兵位 的,所以我们需要先让 lessHeadgreaterHead 指向 哨兵位下一个节点
 
然后再用 链表 1lessTail 去链接 链表 2greaterHead

3. 代码实现

接口代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        
        lessTail->next = greaterTail->next = NULL;
        
        struct ListNode* cur = pHead;
        
        while (cur) {
            if (cur->val < x) {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            else {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greaterHead);
        
        return list;
    }
};

提交结果
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/80882.html

(0)
小半的头像小半

相关推荐

极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!