题目： 现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
文章图片
题目分析： 【程序员面试宝典|【程序员面试宝典】链表分割】解决这个问题采用的方法是：
把比x小的值插入到一个链表，
把比x大的值插入到一个链表，
再把两个链表连接到一起。
代码实现：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
struct ListNode* lessHead,*lessTail,*greaterHead,*greaterTail;
lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = pHead;
while(cur)
{
if(cur->valnext = cur;
lessTail = cur;
}
else
{
greaterTail->next = cur;
greaterTail = cur;
}
cur = cur->next;
}
//切记把最后一个的next置成空。
greaterTail->next = NULL;
lessTail->next = greaterHead ->next;
struct ListNode* head = lessHead->next;
free(lessHead);
free(greaterHead);
return head;
}
};
推荐阅读
- 数据结构|数据结构 链表 合并两个有序的单链表 C语言版
- 笔记|C语言版单链表的建立方式
- 数据结构（C语言实现）|顺序表C语言版
- 数据结构与算法|C语言 创建单链表
- 数据结构|C语言单链表定义及各类操作
- 数据结构|反向遍历单链表 C语言版
- 数据结构|3000字带你深入理解二叉树（图解剖析）
- 链表|栈和队列(跑路人笔记)
- 链表|顺序表代码实现（跑路人笔记）