LeetCode //C - 86. Partition List-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 86. Partition List。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

86. Partition List

Given the head of 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.

Example 1:

LeetCode //C - 86. Partition List,LeetCode,leetcode,c语言,算法

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

From: LeetCode
Link: 86. Partition List

Solution:

Ideas：

The main idea behind the code is to maintain two separate linked lists:

Smaller List: This list contains all the nodes with values smaller than x.
Greater or Equal List: This list contains all the nodes with values greater than or equal to x.

The code does the following:

Initialization

We initialize two “dummy” nodes (smallerHead and greaterHead) to serve as the starting points for the two new lists. Dummy nodes simplify the code by eliminating special cases for the head nodes of the lists.

Traversal

We then traverse the original list (head). For each node:

If its value is smaller than x, we add it to the end of the “Smaller List” and move the smaller pointer ahead.
Otherwise, we add it to the end of the “Greater or Equal List” and move the greater pointer ahead.

Concatenation

Once we’ve gone through all the nodes, we concatenate the “Smaller List” and the “Greater or Equal List” by setting the next of the last node in the “Smaller List” to the first node in the “Greater or Equal List”.

Cleanup文章来源地址https://www.toymoban.com/news/detail-689462.html

Finally, we return the node following the smallerHead dummy node as the new head of the combined list. We also free the memory allocated for the dummy nodes.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    // Initialize two new dummy nodes to serve as the starting points for the two new lists.
    struct ListNode *smallerHead = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *greaterHead = (struct ListNode *)malloc(sizeof(struct ListNode));
    smallerHead->val = 0;
    greaterHead->val = 0;
    smallerHead->next = NULL;
    greaterHead->next = NULL;
    
    struct ListNode *smaller = smallerHead;
    struct ListNode *greater = greaterHead;
    
    // Traverse the original list
    while (head != NULL) {
        if (head->val < x) {
            smaller->next = head;
            smaller = smaller->next;
        } else {
            greater->next = head;
            greater = greater->next;
        }
        head = head->next;
    }
    
    // Connect the two lists
    smaller->next = greaterHead->next;
    greater->next = NULL;
    
    // The new head of the list is the node following the smaller dummy node.
    struct ListNode *newHead = smallerHead->next;
    
    // Free the dummy nodes
    free(smallerHead);
    free(greaterHead);
    
    return newHead;
}