题目描述

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

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

例如：

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

思路分析

本题要求按照某个条件将链表分成两部分，可以采用双指针的方法实现，跑一遍循环，小于 x 的元素放在前面，大于等于 x 的元素放在后面。

具体实现步骤如下：

1. 实例化两个链表：lessList 用于存放小于 x 的值，greaterList 用于存放大于等于 x 的值。

2. 遍历原链表，将小于 x 的值拼接到 lessList 上，将大于等于 x 的值拼接到 greaterList 上。

3. 将 greaterList 链接到 lessList 的末尾，返回 lessList。

代码实现

public ListNode partition(ListNode head, int x) {
    ListNode lessList = new ListNode(0); // 存放小于 x 的链表
    ListNode greaterList = new ListNode(0); // 存放 >= x 的链表
    ListNode lessCur = lessList; // 定义 lessList 指针
    ListNode greaterCur = greaterList; // 定义 greaterList 指针

    // 遍历原链表，根据值大小拼接链表
    while (head != null) {
        if (head.val < x) {
            lessCur.next = head;
            lessCur = lessCur.next;
        } else {
            greaterCur.next = head;
            greaterCur = greaterCur.next;
        }
        head = head.next;
    }

    // 链接 lessList 和 greaterList
    greaterCur.next = null;
    lessCur.next = greaterList.next;
    return lessList.next;
}

时间复杂度分析

该算法仅遍历链表一次，所以时间复杂度为 O(n)。

测试例子

输入：1->4->3->2->5->2，x = 3 输出：1->2->2->4->3->5

输入：1->2->3，x = 4 输出：1->2->3

输入：5->4->3->2->1，x = 3 输出：2->1->5->4->3

扩展点

不同语言的实现

Python：

def partition(self, head: ListNode, x: int) -> ListNode:
    less_list = ListNode(0)
    greater_list = ListNode(0)
    less_cur, greater_cur = less_list, greater_list

    while head:
        if head.val < x:
            less_cur.next = head
            less_cur = less_cur.next
        else:
            greater_cur.next = head
            greater_cur = greater_cur.next
        head = head.next

    greater_cur.next = None
    less_cur.next = greater_list.next
    return less_list.next

C++：

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* less_list = new ListNode(0); // 存放小于 x 的链表
        ListNode* greater_list = new ListNode(0); // 存放 >= x 的链表
        ListNode* less_cur = less_list; // 定义 lessList 指针
        ListNode* greater_cur = greater_list; // 定义 greaterList 指针

        // 遍历原链表，根据值大小拼接链表
        while (head != nullptr) {
            if (head->val < x) {
                less_cur->next = head;
                less_cur = less_cur->next;
            } else {
                greater_cur->next = head;
                greater_cur = greater_cur->next;
            }
            head = head->next;
        }

        // 链接 lessList 和 greaterList
        greater_cur->next = nullptr;
        less_cur->next = greater_list->next;
        return less_list->next;
    }
};

对数据结构的深入理解和介绍

链表是一种常用的数据结构，其特点是节点不连续，每个节点存储了下一个节点的指针，因此可扩展性很强，但也更加复杂。在实际应用中，适用于需要频繁进行插入和删除操作的场合。常用的链表包括单向链表、双向链表、循环链表等。

总结

分隔链表是关于链表的一道经典难题，考察的是对链表的基本操作和指针运用能力。通过本题的实现，我们不仅可以掌握基本的链表操作技巧，还可以更全面地了解和掌握数据结构链表的概念和应用。此外，通过编写代码实现，也可以更深刻地理解时间和空间复杂度的概念，从而更好地提升编程和算法能力。