题目描述

题目链接：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.

例子

例子 1

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

例子 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

解题思路

这道题要求给定一个节点和一个值 x，将链表分成两部分：小于 x 和大于等于 x 的，并且两部分内部相对顺序保持不变。思路比较简单，遍历一次原链表，用两个链表分成存储这两部分，最后将前者的尾部和后者的头部相连即可，注意一下最后需要将第二段链表的尾部的下一个节点置空。代码如下：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* less_list = new ListNode();
        ListNode* less_tail = less_list;
        ListNode* greater_list = new ListNode();
        ListNode* greater_tail = greater_list;
        ListNode* curr = head;
        while (curr) {
            if (curr->val < x) {
                less_tail->next = curr;
                less_tail = curr;
            } else {
                greater_tail->next = curr;
                greater_tail = curr;
            }
            curr = curr->next;
        }
        less_tail->next = greater_list->next;
        return less_list->next;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

GitHub 代码同步地址： 86.PartitionList.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions