LeetCode面试题02.04分割链表和86分隔链表题解总结_86分隔链表示例

面试题02.04、分割链表

其实我自己一开始看到这个题目的时候，是一脸懵* 的，后来结合着英文版的题目，才把题目意思给搞懂。个人觉得，主要是这个示例整的，让人有点迷。我觉得应该加上一句：答案不唯一或者左右部分内部节点无顺序要求。（即不必考虑元素的相对位置）

题目的意思就是：把小于x的节点放在大于或等于x对的节点的前面。
例如： [1,4,3,2,5,2] 3 -> [1, 2, 2, 3, 4, 5]
[3, 5, 8, 5, 10, 2, 1] 5 -> [1, 2, 3, 5, 5, 8, 10]

方法：双指针
cur是遍历的当前节点，pre为遍历中第一个未交换的节点。
cur向后遍历过程中，若遇到小于x的元素，就将cur的val与pre的val进行交换；否则，就一直往下遍历，直到链表尾。
例如： [3, 5, 8, 5, 10, 2, 1] 5 -> [3, 2, 1, 5, 10, 5, 8]，个人的思路笔记如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 class Solution{
public:
    void swap(ListNode* pre, ListNode* cur){
        if(pre == NULL || cur == NULL)   return;
        int tmp = pre->val;
        pre->val = cur->val;
        cur->val = tmp;
    }

    ListNode* partition(ListNode* head, int x){
        if(head == NULL)  return NULL;   
        ListNode* cur = head;
        ListNode* pre = head;
        while(cur){
            if(cur->val < x){
                swap(pre, cur);
                pre = pre->next;
            }
            cur = cur->next;
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

当然，还有一种做法就是：把小于x的节点都连起来，把不小于x的节点也都连起来，再拼接在一起。这种做法就保持了原链表里的相对顺序。正如下面这题的做法。

86、分隔链表

其实，如果先做这题的话，再做上面那道题，就没那么迷了。这题也比上一道题的要求稍微高一点，就是要保持原链表里的相对顺序。

这里也是使用双指针before和after来追踪上述的两个链表。两个指针用于创建两个链表，一个用于保存原链表中值 < x的元素；另一个用于保存原链表中值 > x的元素。最后将after拼接在before的后面。before_head、after_head是两个链表的头结点。

具体来看：
这里使用LeetCode官方题解的图
1、初始化两个指针 before 和 after。在实现中，将两个指针初始化为哑 ListNode，这有助于减少条件判断。

2、利用head指针遍历原链表。

3、若head指针指向的元素值 < x，该节点应当是before链表的一部分。因此，将其移到before中。

4、否则，该节点应当是after链表的一部分。因此，将其移到after中。

5、遍历完原有链表的全部元素之后，我们得到了两个链表 before 和 after。原有链表的元素或者在before 中或者在 after 中，这取决于它们的值。

6、现在，将after接在before后面，组成所求的链表。由于从左到右遍历原链表，故两个链表中元素的相对顺序不会发生改变。

注：为了算法实现更容易，我们使用了哑结点初始化。不能让哑结点成为返回链表中的一部分，因此在组合两个链表时需要向前移动一个节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL || head->next == NULL)  return head;
    ListNode* before_head = (ListNode*)malloc(sizeof(ListNode));
    before_head->val = 0;
    ListNode* before = before_head;
    ListNode* after_head = (ListNode*)malloc(sizeof(ListNode));
    after_head->val = 0;
    ListNode* after = after_head;
    ListNode* p = head;
    while(p){
        if(p->val < x){
            before->next = p;
            before = before->next;
        }
        else{
            after->next = p;
            after = after->next;
        }
        p = p->next;
    }
    after->next = NULL;
    before->next = after_head->next;
   
    return before_head->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

复杂度分析

时间复杂度: O(N)，其中N是原链表的长度，对该链表进行了遍历。

空间复杂度: O(1)，只移动了原有的结点，因此没有使用任何额外空间。