LeetCode_86_PartitionList

2019 年 03 月 29 日

840 次浏览

3708字数

1. 题目描述

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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

2. 初解

说一下我拿到这道题的时候的解题思路，首先注意题目中有个要求，保持链表中的相对顺序不变，这也就是例子里面的Output的1->2->2->4->3->5的顺序的由来。

首先感性的模拟一下这个output是怎么得来的，首先判断1，比3小但此时我们的结果链表中只有这一个元素所以不用动，然后判断4，比3大但此时比3小的只有一个1而且已经在4左边了所以不用动，然后3也是类似的过程。这时候最关键的判断2来了，比3小，所以要把它移到所有的比3大的节点的左边，可以想到就是直接移到1的后面，而让原来2前面的3接上后面的5。后面的5和2也是类似的过程。

将这个思路转化成程序的思维就是，用一个指针prev记录最后一个比x小的元素的位置，每再次找到一个比x小的元素就把那个元素接在prev的后面。再用一个指针curr记录下一个要判断的元素的前一个结点，之所以是前一个结点是因为如果下一个要判断的元素小于x它就要被移走，而所以需要这个元素的前一个元素的指针来让前一个元素的next指向next的next。而如果curr的下一个元素比x大，就只用让curr=curr->next就行了。

最近迷上了画图解题，所以下面再用图像来表示一下这种解题思路。

首先空心圆表示比x小的元素，实心圆表示比x大的元素，现在看curr的指向，curr->next比x小，所以首先，将这个元素移到Prev的后面

然后让Prev=Prev->next就ok了。注意这种情况下最后Curr的指向不用变，因为此时Curr->next依旧是下一个要判断的元素。

但关键的地方是这个方法有一个漏洞，即如果暂时还没出现比x大的元素，即下面这种情况

可以想到此时Prev和Curr的指向是相同的，因为此时这个元素既是最后一个比x小的元素，又是要判断的下一个元素的前一个元素。然后进行上面的解题步骤，判断下一个元素，可以发现一轮流程走完会变成下面这样

Curr的指向不对了，所以最后在程序里额外判断一下这种情况，然后让Curr再等与Prev就可以了。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* prev = dummyHead;  // prev指向最后一个比x小的元素
    struct ListNode* curr = dummyHead;  // curr指向下一个要判断的元素的前一个元素
    struct ListNode* tmp;

    while (curr->next != NULL) {
        if (curr->next->val < x) {  // 下一个要判断的元素比x小
            tmp = curr->next;
            curr->next = curr->next->next;
            tmp->next = prev->next;
            prev->next = tmp;
            prev = prev->next;
            if (prev == curr->next)  // 处理暂时全都是比x小的元素这种特殊情况
                curr = prev;
        }
        else {
            curr = curr->next;
        }
    }

    return dummyHead->next;
}

struct ListNode* CreatLL(int* arr, int size) {
    struct ListNode* dummyHead =
        (struct ListNode *)malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = NULL;
    struct ListNode* ptr = dummyHead;
    struct ListNode* tmp;

    for (int i = 0; i < size; i++) {
        tmp = (struct ListNode *)malloc(sizeof(struct ListNode));
        tmp->next = NULL;
        tmp->val = arr[i];
        ptr->next = tmp;
        ptr = ptr->next;
    }

    return dummyHead->next;
}

void printLL(struct ListNode* head) {
    struct ListNode* ptr = head;
    while (ptr) {
        printf("%d -> ", ptr->val);
        ptr = ptr->next;
    }
    putchar('\n');
}

int main() {
    int arr[] = { 1, 4, 3, 2, 5, 2 };
    struct ListNode* head = CreatLL(arr, 6);
    printLL(head);
    head = partition(head, 3);
    printLL(head);

    system("pause");
    return 0;
}

4. 精彩解法

LeetCode上大神云集，同样有人给出了一个Smart的解法

ListNode *partition(ListNode *head, int x) {
    ListNode node1(0), node2(0);
    ListNode *p1 = &node1, *p2 = &node2;
    while (head) {
        if (head->val < x)
            p1 = p1->next = head;
        else
            p2 = p2->next = head;
        head = head->next;
    }
    p2->next = NULL;
    p1->next = node2.next;
    return node1.next;
}

简短且巧妙，核心思想和我的解法一样，但这种解法不用拘泥于每次移动节点还要把链表重新拼接起来组成一个完整的链表，而是用巧妙地方式将比x大的一部分的头节点记录下来，并把比x小的一部分的头节点也记录下来，最终全部遍历完了再拼接。而且也不用dummyHead之类的来处理特殊情况。

LeetCode_86_PartitionList