内容简介:本文首发于公众号「五分钟学算法」,是个人网站:www.cxyxiaowu.com题目来源于 LeetCode 上第 86 号问题:分割链表。题目难度为 Easy,目前通过率为 47.8% 。
本文首发于公众号「五分钟学算法」,是 图解 LeetCode 系列文章之一。
个人网站:www.cxyxiaowu.com
题目来源于 LeetCode 上第 86 号问题:分割链表。题目难度为 Easy,目前通过率为 47.8% 。
题目描述
给定一个链表和一个特定值 x ,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 复制代码
题目解析
这道题要求我们划分链表,把所有小于给定值的节点都移到前面,大于该值的节点顺序不变,相当于一个局部 排序 的问题。
- 设定两个虚拟节点,
dummyHead1
用来保存小于于该值的链表,dummyHead2
来保存大于等于该值的链表 - 遍历整个原始链表,将小于该值的放于
dummyHead1
中,其余的放置在dummyHead2
中 - 遍历结束后,将
dummyHead2
插入到dummyHead1
后面
动画描述
代码实现
class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* dummyHead1 = new ListNode(-1); ListNode* dummyHead2 = new ListNode(-1); ListNode* prev1 = dummyHead1; ListNode* prev2 = dummyHead2; for(ListNode* cur = head ; cur != NULL ;){ if(cur->val < x){ prev1->next = cur; cur = cur->next; prev1 = prev1->next; prev1->next = NULL; } else{ prev2->next = cur; cur = cur->next; prev2 = prev2->next; prev2->next = NULL; } } prev1->next = dummyHead2->next; ListNode* ret = dummyHead1->next; delete dummyHead1; delete dummyHead2; return ret; } }; 复制代码
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 【图像分割】图像分割专栏栏主自述:分割,我们究竟在研究什么?
- 【图像分割模型】用BRNN做分割—ReSeg
- 语义分割:GSCNN 提高边缘和小目标的分割性能
- 语义分割领域开山之作:Google提出用神经网络搜索实现语义分割
- 【图像分割模型】BRNN下的RGB-D分割—LSTM-CF
- 分割算法总结
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Data Structures and Algorithms in Python
Michael T. Goodrich、Roberto Tamassia、Michael H. Goldwasser / John Wiley & Sons / 2013-7-5 / GBP 121.23
Based on the authors' market leading data structures books in Java and C++, this book offers a comprehensive, definitive introduction to data structures in Python by authoritative authors. Data Struct......一起来看看 《Data Structures and Algorithms in Python》 这本书的介绍吧!
MD5 加密
MD5 加密工具
XML、JSON 在线转换
在线XML、JSON转换工具