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的结点加入左链表中，否则将结点加入右链表中，最后将两个链表串联起来就OK了。
解题
c++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode dummy1(-1),dummy2(-1);
ListNode *left=&dummy1,*right=&dummy2;
ListNode *left_cur=left,*right_cur=right;
ListNode *cur=head;
while(cur){
if(cur->val<x){
left_cur->next=cur;
left_cur=cur;
cur=cur->next;
}
else{
right_cur->next=cur;
right_cur=cur;
cur=cur->next;
}
}
left_cur->next=right->next;
right_cur->next=NULL;
return left->next;
}
};
|
python版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution:
def partition(self, head, x):
left=ListNode(-1)
right=ListNode(-1)
left_cur=left
right_cur=right
cur=head
while cur:
if cur.val<x:
left_cur.next=cur
left_cur=cur
else:
right_cur.next=cur
right_cur=cur
cur=cur.next
left_cur.next=right.next
right_cur.next=None
return left.next
|
