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的节点的相对顺序不变,大于等于x的节点的相对顺序不变.
--------------
思路:
和奇数偶数排序一样类似,
遍历链表的时候,将节点分组,
难点在于怎么判断开始?怎么判断链表结束?
定义两个假的头节点dummy1,dummy2,利用两个p1和p2分别指向前两个节点
外加一个遍历list的指针curr,
最后将dummy1链表的尾指向dummy2链表的头节点(这里dummy1和dummy2都是节点,不是指针).
代码如下:
/**
* 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) {
if(head==nullptr || head->next==nullptr) return head;
ListNode *head1,*head2;
ListNode *p1,*p2,*curr;
ListNode dummy1(-);
ListNode dummy2(-);
curr = head;
p1 = head1 = &dummy1;
p2 = head2 = &dummy2; while(curr){
if(curr->val < x){
p1->next = curr;
p1 = p1->next;
//p1->next = nullptr;
}else{
p2->next = curr;
p2 = p2->next;
//p2->next = nullptr;
}
curr = curr->next;
}
p1->next = nullptr;
p2->next = nullptr;
//showList(head1->next);
//showList(head2->next); p1->next = head2->next;
return head1->next;
}
};