86.分隔链表

发表于 | 分类于
字数统计: 357 | 阅读时长 ≈ 1

一、题目描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

1
2
3
4
5
6
7
8
9
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

二、题解

1.算法描述

  • 迭代

2.个人分析

  1. 用head指针遍历链表，并申请两个节点；
  2. 比x大的节点接在smaller后边；比x小的节点接在bigger后边；
  3. 吧bigger接在smaller后边。

3.代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *partition(struct ListNode *head, int x)
{
    struct ListNode *smaller = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *bigger = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *p = smaller, *q = bigger;
    while (head)
    {
        if (head->val < x)
        {
            p->next = head;
            p = p->next;
        }
        else
        {
            q->next = head;
            q = q->next;
        }
        head = head->next;
    }
    q->next = NULL;
    p->next = bigger->next;
    return smaller->next;
}