[LeetCode] Partition List 划分链表
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2
and x = 3,
return 1->2->2->4->3->5
.
这道题要求我们划分链表,把所有小于给定值的节点都移到前面,大于该值的节点顺序不变,相当于一个局部排序的问题。那么可以想到的一种解法是首先找到第一个大于或等于给定值的节点,用题目中给的例子来说就是先找到4,然后再找小于3的值,每找到一个就将其取出置于4之前即可,代码如下:
解法一
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *dummy = new ListNode(-);
dummy->next = head;
ListNode *pre = dummy, *cur = head;;
while (pre->next && pre->next->val < x) pre = pre->next;
cur = pre;
while (cur->next) {
if (cur->next->val < x) {
ListNode *tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
pre = pre->next;
} else {
cur = cur->next;
}
}
return dummy->next;
}
};
这种解法的链表变化顺序为:
1 -> 4 -> 3 -> 2 -> 5 -> 2
1 -> 2 -> 4 -> 3 -> 5 -> 2
1 -> 2 -> 2 -> 4 -> 3 -> 5
此题还有一种解法,就是将所有小于给定值的节点取出组成一个新的链表,此时原链表中剩余的节点的值都大于或等于给定值,只要将原链表直接接在新链表后即可,代码如下:
解法二
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
if (!head) return head;
ListNode *dummy = new ListNode(-);
ListNode *newDummy = new ListNode(-);
dummy->next = head;
ListNode *cur = dummy, *p = newDummy;
while (cur->next) {
if (cur->next->val < x) {
p->next = cur->next;
p = p->next;
cur->next = cur->next->next;
p->next = NULL;
} else {
cur = cur->next;
}
}
p->next = dummy->next;
return newDummy->next;
}
};
此种解法链表变化顺序为:
Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2
New:
Original: 4 -> 3 -> 2 -> 5 -> 2
New: 1
Original: 4 -> 3 -> 5 -> 2
New: 1 -> 2
Original: 4 -> 3 -> 5
New: 1 -> 2 -> 2
Original:
New: 1 -> 2 -> 2 -> 4 -> 3 -> 5
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- [转载]C/C++框架和库
- asp.net报错“尝试读取或写入受保护的内存。这通常指示其他内存已损坏”的解决办法
- linux下如何安装webbench
- 解决IIS7.0服务和用户上传的文件分别部署在不同的电脑上时,解决权限的问题
- ReactiveCocoa(RAC)
- markdown编辑器实现笔记
- Socket与TcpClient的区别(转载)
- json化表单数据
- Android 线程Thread的2种实现方法
- 前端leader找我谈心:我是如何从刚毕业的前端菜鸟一步步成长为前端架构师的?
- 普通Linux用户1分钟上手vi编辑器
- 20175213吕正宏 MyCP(课下任务,必做)
- 6486: An Ordinary Game(规律)
- 使用 Immutable Subject 来驱动 Angular 应用
- CAN总线中节点ID相同会怎样?
- 记一次SQL注入实战
- PHP 数字序数&;字母序数 相互转化
- chrome表单自动填充导致input文本框背景变成偏黄色问题解决
- spyder快捷键
- [QT_OPENCV] qt下opencv配置以及首个opencv工程
热门文章
- 使用session页面控制登录入口及购物车效果的实现
- 3.C#面向对象基础聊天机器人
- 账号密码管理系统Access版本
- 用SignalR 2.0开发客服系统[系列2:实现聊天室]
- 我看不下去鸟。。。。Java和C#的socket通信真的简单吗?
- Angular2 小贴士 Name
- Mac制作U盘系统(OS X El Capitan)教程
- Entity Framework Code First Migrations--EF 的数据迁移
- Maven+Spring+Spring MVC+MyBatis+MySQL,搭建SSM框架环境【转】
- 【JS基础】算法