作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。
输入格式
- head：链表的头节点。
- x：分隔值。
输出格式
- 返回重新排列后的链表的头节点。
示例
示例 1
输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
方法一：使用两个指针
解题步骤
- 创建两个链表：一个用于存放小于
x的节点，另一个用于存放大于等于x的节点。 - 合并链表：遍历原链表，根据节点值将节点分配到两个链表中，然后将这两个链表合并。
完整的规范代码
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def partition(head, x): """ 使用两个指针分隔链表 :param head: ListNode, 链表的头节点 :param x: int, 分隔值 :return: ListNode, 分隔后的链表头节点 """ less_head = ListNode(0) # 小于x的链表虚拟头节点 greater_head = ListNode(0) # 大于等于x的链表虚拟头节点 less = less_head greater = greater_head while head: if head.val < x: less.next = head less = less.next else: greater.next = head greater = greater.next head = head.next # 合并两个链表 greater.next = None # 防止构成环 less.next = greater_head.next return less_head.next # 示例调用 # 假设创建链表函数和打印函数已定义
算法分析
- 时间复杂度：(O(n))，其中 (n) 是链表的长度，需要遍历一次链表。
- 空间复杂度：(O(1))，使用了常数个额外指针。
方法二：原地重排
解题步骤
- 使用四个指针：
less_start,less_end,greater_start,greater_end分别标记两个部分的开始和结束位置。 - 节点交换：遍历链表，根据节点的值决定其应该放置的位置，并相应地移动指针。
完整的规范代码
def partition(head, x): """ 原地重排链表，保留节点的相对位置 :param head: ListNode, 链表的头节点 :param x: int, 分隔值 :return: ListNode, 分隔后的链表头节点 """ if not head or not head.next: return head dummy = ListNode(0) dummy.next = head prev = dummy curr = head # 寻找第一个大于等于x的节点 while curr and curr.val < x: prev = curr curr = curr.next # 如果已经是排好序或没有需要移动的节点 if not curr or not curr.next: return dummy.next # 遍历剩余节点 node_to_move = curr.next node_to_move_prev = curr while node_to_move: if node_to_move.val < x: # 移动节点到前半部分 node_to_move_prev.next = node_to_move.next node_to_move.next = curr prev.next = node_to_move # 更新指针 prev = node_to_move node_to_move = node_to_move_prev.next else: node_to_move_prev = node_to_move node_to_move = node_to_move.next return dummy.next # 示例调用 # 假设创建链表函数和打印函数已定义
算法分析
- 时间复杂度：(O(n))，必须遍历整个链表。
- 空间复杂度：(O(1))，原地修改，没有使用额外空间。
方法三：收集节点后重建
解题步骤
- 收集节点：遍历链表，将小于
x的节点放入一个列表，大于等于x的节点放入另一个列表。 - 重建链表：首先链接小于
x的节点，然后链接大于等于x的节点，最后返回新链表的头节点。
完整的规范代码
def partition(head, x): """ 收集节点后重建链表 :param head: ListNode, 链表的头节点 :param x: int, 分隔值 :return: ListNode, 分隔后的链表头节点 """ less_nodes = [] greater_nodes = [] node = head while node: if node.val < x: less_nodes.append(node) else: greater_nodes.append(node) node = node.next # 重建链表 dummy = ListNode(0) curr = dummy for node in less_nodes + greater_nodes: curr.next = node curr = curr.next curr.next = None return dummy.next # 示例调用 # 假设创建链表函数和打印函数已定义
算法分析
- 时间复杂度：(O(n))，遍历链表一次，并重新构建链表一次。
- 空间复杂度：(O(n))，存储节点的列表可能与链表长度相同。
方法四：原地重排优化
解题步骤
- 直接在遍历中分离节点：利用两个虚拟头节点
less_head和greater_head分别连接小于x和大于等于x的节点。 - 尾部处理：确保所有处理后的链表没有形成环。
完整的规范代码
def partition(head, x): """ 原地重排优化，避免额外空间使用 :param head: ListNode, 链表的头节点 :param x: int, 分隔值 :return: ListNode, 分隔后的链表头节点 """ # 创建两个虚拟头节点 less_head = ListNode(0) greater_head = ListNode(0) less = less_head greater = greater_head # 遍历原链表，根据x值分配节点到两个部分 while head: if head.val < x: less.next = head less = less.next else: greater.next = head greater = greater.next head = head.next # 防止环的产生 greater.next = None # 连接两部分 less.next = greater_head.next return less_head.next # 示例调用 # 假设创建链表函数和打印函数已定义
算法分析
- 时间复杂度：(O(n))，遍历一次链表。
- 空间复杂度：(O(1))，虽然使用了两个额外的头节点，但整体上仍为常数级额外空间。
方法五：递归法
解题步骤
- 递归遍历：递归处理链表节点，根据节点值与
x的比较决定其归属。 - 合并：递归过程中自然合并符合条件的节点。
完整的规范代码
def partition(head, x): """ 递归方法重排链表 :param head: ListNode, 链表的头节点 :param x: int, 分隔值 :return: ListNode, 分隔后的链表头节点 """ if not head or not head.next: return head # 将头节点后面的节点进行分隔 next_partitioned = partition(head.next, x) if head.val < x: head.next = next_partitioned return head else: # 找到分隔后的链表中第一个小于x的节点前的节点 last_less = None current = next_partitioned while current and current.val >= x: last_less = current current = current.next if last_less: head.next = last_less.next last_less.next = head else: head.next = next_partitioned return head return next_partitioned # 示例调用 # 假设创建链表函数和打印函数已定义
算法分析
- 时间复杂度：(O(n))，每个节点访问一次。
- 空间复杂度：(O(n))，由于递归的深度可能达到链表的长度。
不同算法的优劣势对比
| 特征 | 方法一：使用两个指针 | 方法二：原地重排 | 方法三：收集节点后重建 | 方法四：原地重排优化 | 方法五：递归法 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(n)) | (O(1)) | (O(n)) |
| 优势 | 简单明了，易于理解 | 不需要额外空间，直观 | 直接操作，易于实现 | 极少额外空间，效率高 | 自然合并，逻辑简单 |
| 劣势 | 代码较长，需要处理多个节点连接 | 较复杂，需要正确处理边界 | 使用额外空间存储节点 | 需要处理更多的边界条件 | 可能导致栈溢出，效率低于迭代 |
应用示例
这些方法可以应用于数据流分离、系统优先级调度、社交网络中的数据分级处理等多个领域，特别是在需要根据特定规则组织数据时。
欢迎关注微信公众号 数据分析螺丝钉
