[LeetCode] List Dividing Link 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.
This question requires us to divide the linked list and move all nodes smaller than the given value to the front. The order of nodes larger than the value remains unchanged, which is equivalent to a problem of local sorting. Then one solution that can be imagined is to first find the first node greater than or equal to the given value. To use the example given in the question, it is to find 4 first, and then find a value less than 3. Each time it is found, it is taken out and placed before 4. The code is as follows:
Solution 1
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *pre = dummy, *cur = head;;
while (pre->next && pre->next->val < x) pre = pre->next;
cur = pre;
while (cur->next) {
if (cur->next->val < x) {
ListNode *tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
pre = pre->next;
} else {
cur = cur->next;
}
}
return dummy->next;
}
};
The order of change of the linked list of this solution is:
1 -> 4 -> 3 -> 2 -> 5 -> 2
1 -> 2 -> 4 -> 3 -> 5 -> 2
1 -> 2 -> 2 -> 4 -> 3 -> 5
There is another solution to this problem, which is to take out all nodes smaller than the given value to form a new linked list. At this time, the values of the remaining nodes in the original linked list are greater than or equal to the given value. Just connect the original linked list directly to the new linked list. The code is as follows:
Solution 2
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
if (!head) return head;
ListNode *dummy = new ListNode(-1);
ListNode *newDummy = new ListNode(-1);
dummy->next = head;
ListNode *cur = dummy, *p = newDummy;
while (cur->next) {
if (cur->next->val < x) {
p->next = cur->next;
p = p->next;
cur->next = cur->next->next;
p->next = NULL;
} else {
cur = cur->next;
}
}
p->next = dummy->next;
return newDummy->next;
}
};
The order of change of this solution list is:
Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2
New:
Original: 4 -> 3 -> 2 -> 5 -> 2
New: 1
Original: 4 -> 3 -> 5 -> 2
New: 1 -> 2
Original: 4 -> 3 -> 5
New: 1 -> 2 -> 2
Original:
New: 1 -> 2 -> 2 -> 4 -> 3 -> 5
This is the article about C++ implementation of LeetCode (86. Dividing Linked List). For more related contents of C++ implementation of linkage, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!