LeetCode 题目 86:分隔链表

简介: LeetCode 题目 86:分隔链表

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给你一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

输入格式
  • head:链表的头节点。
  • x:分隔值。
输出格式
  • 返回重新排列后的链表的头节点。

示例

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

方法一:使用两个指针

解题步骤
  1. 创建两个链表:一个用于存放小于 x 的节点,另一个用于存放大于等于 x 的节点。
  2. 合并链表:遍历原链表,根据节点值将节点分配到两个链表中,然后将这两个链表合并。
完整的规范代码
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)),使用了常数个额外指针。

方法二:原地重排

解题步骤
  1. 使用四个指针less_start, less_end, greater_start, greater_end 分别标记两个部分的开始和结束位置。
  2. 节点交换:遍历链表,根据节点的值决定其应该放置的位置,并相应地移动指针。
完整的规范代码
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)),原地修改,没有使用额外空间。

方法三:收集节点后重建

解题步骤
  1. 收集节点:遍历链表,将小于 x 的节点放入一个列表,大于等于 x 的节点放入另一个列表。
  2. 重建链表:首先链接小于 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)),存储节点的列表可能与链表长度相同。

方法四:原地重排优化

解题步骤
  1. 直接在遍历中分离节点:利用两个虚拟头节点less_headgreater_head分别连接小于x和大于等于x的节点。
  2. 尾部处理:确保所有处理后的链表没有形成环。
完整的规范代码
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)),虽然使用了两个额外的头节点,但整体上仍为常数级额外空间。

方法五:递归法

解题步骤
  1. 递归遍历:递归处理链表节点,根据节点值与x的比较决定其归属。
  2. 合并:递归过程中自然合并符合条件的节点。
完整的规范代码
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))
优势 简单明了,易于理解 不需要额外空间,直观 直接操作,易于实现 极少额外空间,效率高 自然合并,逻辑简单
劣势 代码较长,需要处理多个节点连接 较复杂,需要正确处理边界 使用额外空间存储节点 需要处理更多的边界条件 可能导致栈溢出,效率低于迭代

应用示例

这些方法可以应用于数据流分离、系统优先级调度、社交网络中的数据分级处理等多个领域,特别是在需要根据特定规则组织数据时。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
20天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
16 2
|
20天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
20天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
26天前
|
C语言
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
详解Leetcode中关于malloc模拟开辟二维数组问题,涉及二维数组的题目所给函数中的各个参数的解读
11 1
|
11天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
19 2
|
1月前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
20天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题