To solve this problem, we need to partition a linked list around a given value (x) such that all nodes with values less than (x) come before nodes with values greater than or equal to (x), while preserving the original order of nodes in each partition.

Approach

The key idea is to split the linked list into two separate lists:

1. Less List: Contains nodes with values less than (x).
2. Greater List: Contains nodes with values greater than or equal to (x).

We then connect these two lists to form the final partitioned list. Here are the detailed steps:

1. Initialize Pointers: For both the less and greater lists, we maintain head and tail pointers to efficiently append nodes.
2. Traverse Original List: For each node, append it to either the less list or the greater list based on its value relative to (x).
3. Break Links: After appending a node to either list, break its link to the next node to avoid cycles.
4. Connect Lists: If the less list is non-empty, connect its tail to the head of the greater list. Ensure the tail of the greater list points to NULL to terminate the list properly.

Solution Code

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL) return NULL;
    struct ListNode *less = NULL, *less_tail = NULL;
    struct ListNode *greater = NULL, *greater_tail = NULL;
    struct ListNode *current = head;

    while (current != NULL) {
        if (current->val < x) {
            if (less == NULL) {
                less = current;
                less_tail = current;
            } else {
                less_tail->next = current;
                less_tail = current;
            }
        } else {
            // Fill in blank (1)
            if (greater == NULL) {
                greater = current;
                greater_tail = current;
            } else {
                greater_tail->next = current;
                greater_tail = current;
            }
        }
        // Fill in blank (2)
        struct ListNode* next = current->next;
        current->next = NULL;
        current = next;
    }

    if (less == NULL) {
        return greater;
    } else {
        less_tail->next = greater;
        return less;
    }
}

Explanation

1. Blank (1): This part handles appending nodes to the greater list. If the greater list is empty, we initialize its head and tail to the current node. Otherwise, we append the current node to the tail of the greater list and update the tail pointer.
2. Blank (2): This part saves the next node, breaks the link between the current node and its next node (to avoid cycles), and moves the current pointer to the next node in the original list.

This approach ensures that the original order of nodes is preserved in each partition, and the time complexity is (O(n)) where (n) is the number of nodes in the linked list, as we traverse each node exactly once. The space complexity is (O(1)) since we only use a constant number of additional pointers.

Answer:
The code for blank (1) is:

if (greater == NULL) {
    greater = current;
    greater_tail = current;
} else {
    greater_tail->next = current;
    greater_tail = current;
}

The code for blank (2) is:

struct ListNode* next = current->next;
current->next = NULL;
current = next;

These fill-ins complete the partition function correctly. The final answer is the combination of these two code snippets as shown above.

if (greater == NULL) {
    greater = current;
    greater_tail = current;
} else {
    greater_tail->next = current;
    greater_tail = current;
}
struct ListNode* next = current->next;
current->next = NULL;
current = next;

作者声明:本文包含人工智能生成内容。