How to solve the problems related to Partition

This article mainly explains "how to solve Partition-related problems". Friends who are interested may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to solve Partition-related problems.

Meaning of the title:

According to the given linked list and the given value X, put those greater than X on the right side of X and those less than X on the left side of X. Do not change the relative position, for example, 4 and 3 are greater than or equal to 3, then they move to the right after the position is still 4 in front, 3 in the back.

Train of thought:

1) if the linked list is empty or has only one node, you can return it.

2) define two linked lists list and back, which store the linked list less than X node and the linked list greater than or equal to X respectively. The secondary pointer is used to facilitate the processing of the head node.

3) after the end of the while loop, the next of the last node of the list and back linked list is not set to NULL. So set the back chain trailer node next to NULL. And append back to the end of list.

/ * Definition for singly-linked list. * struct ListNode {* int val; * struct ListNode* next; *}; * / struct ListNode* partition (struct ListNode* head, int x) {if (head = = NULL | | head- > next = = NULL) {return head;} struct ListNode* list = NULL; struct ListNode* * first = & list; struct ListNode* back = NULL; struct ListNode* * second = & back; while (head) {if (head- > val)

< x) { *first = head; first = &(*first)->

Next;} else {* second = head; second = & (* second)-> next;} head = head- > next;} * second = NULL; * first = back; return list;} so far, I believe you have a deeper understanding of "how to solve Partition-related problems". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!