【LeetCode】Partition List ——链表排序问题

发布时间:2017-7-1 10:52:20编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【LeetCode】Partition List ——链表排序问题 ",主要涉及到【LeetCode】Partition List ——链表排序问题 方面的内容,对于【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.

【解析】

题意:给定一个单链表和一个x,把链表中小于x的放到前面,大于等于x的放到后面,每部分元素的原始相对位置不变。

思路:其实很简单,遍历一遍链表,把小于x的都挂到head1后,把大于等于x的都放到head2后,最后再把大于等于的链表挂到小于链表的后面就可以了。

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *partition(ListNode *head, int x) {12         ListNode lessHead(0);13         ListNode greatHead(0);14         ListNode *cur=head,*less=&lessHead,*great=&greatHead;15         while(cur!=NULL){16             ListNode *next=cur->next;17             if(cur->val<x){18                 less->next=cur;19                 less=less->next;20                 less->next=NULL;21             }22             else{23                 great->next=cur;24                 great=great->next;25                 great->next=NULL;26             }27             cur=next;28         }29         less->next=greatHead.next;30         return lessHead.next;31     }32 };


上一篇:linux驱动current,引用当前进程,及task_struct(转)
下一篇:【转】PHP中file_put_contents追加和换行

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款