题解 | 划分链表

解题思路：

如下图所示，题目要求实现链表所有「值 <x 节点」出现在「值 ≥x 节点」前面。

根据题意，考虑通过「新建两个链表」实现原链表分割，算法流程为：

新建两个链表 dummy_l、dummy_r，分别用于添加所有「节点值 <x 」、「节点值 ≥x 」的节点。

遍历链表 head 并依次比较各节点值 head.val 和 x 的大小：

若 head.val < x ，则将节点 head 添加至链表dummy_l 最后面；

若 head.val >= x ，则将节点 head 添加至链表 dummy_r最后面；

遍历完成后，拼接 dummy_l和 dummy_r链表。

最终返回头节点 dummy_l即可。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param x int整型 
# @return ListNode类
#
class Solution:
    def partition(self , head: ListNode, x: int) -> ListNode:
        # write code here
        dummy_l, dummy_r = ListNode(0), ListNode(0)
        l, r, cur = dummy_l, dummy_r, head
        while cur:
            if cur.val<x:
                l.next = cur
                l = l.next
            else:
                r.next = cur
                r = r.next
            cur = cur.next
        r.next = None
        l.next = dummy_r.next
        return dummy_l.next

复杂度分析：

时间复杂度 O(N) ： 其中 N 为链表长度；遍历链表使用线性时间。

空间复杂度 O(1) ： 假头节点使用常数大小的额外空间。