赞
踩
声明:我的链表OJ系列是针对无头单向不循环链表的题目
题目来源:链表分割_牛客题霸_牛客网
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针
创建两个链表,遍历一遍传入的链表,将值大于x的结点和值小于x的结点依次尾插到两个链表中,最后再将这两个链表链接起来,并返回第一个结点的位置即可。
1.把小于x的结点尾插到less链表,把大于x的结点尾插到greater链表。
2.将less链表与greater链表链接起来。
注意:
1.链接后的链表的最后一个结点的指针域需要置空,否则可能造成链表成环。
2.返回的头指针应是lessHead->next,而不是lessHead。
- struct ListNode {
- int val;
- struct ListNode *next;
- ListNode(int x) : val(x), next(NULL) {}
- };
-
- class Partition {
- public:
- ListNode* partition(ListNode* pHead, int x) {
- ListNode* greaterHead, *greaterTail, *lessHead, *lessTail;
- //申请一个头结点,后面链接大于x的结点
- greaterHead = greaterTail = (ListNode*)malloc(sizeof(struct ListNode));
- //申请一个头结点,后面链接小于x的结点
- lessHead = lessTail = (ListNode*)malloc(sizeof(struct ListNode));
- greaterTail->next = NULL;//尾指针的指针域置空
- lessTail->next = NULL;//尾指针的指针域置空
- ListNode* cur = pHead;//接收传入的链表,准备遍历
- while (cur)
- {
- if (cur->val < x)
- {
- //结点值小于x,链接到less链表后面
- lessTail->next = cur;
- lessTail = lessTail->next;
- }
- else
- {
- //结点值大于x,链接到greater链表后面
- greaterTail->next = cur;
- greaterTail = greaterTail->next;
- }
- cur = cur->next;//指针后移,遍历后面的结点
- }
- //将less链表和greater链表链接起来
- lessTail->next = greaterHead->next;//greater链表的第一个结点链接到less链表的尾上
- greaterTail->next = NULL;//将greater链表最后一个结点的指针域置空
- ListNode* head = lessHead->next;//接收链接后链表的第一个结点地址
- free(greaterHead);//释放greater链表的头结点
- free(lessHead);//释放less链表的头结点
- return head;//返回新链表
- }
- };

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。