划分链表

问题简述

给定链表和一个值 x，将所有小于 x 的值移动到左侧，保持相对顺序；

划分链表_牛客题霸_牛客网

思路

• 快排中的 partition 操作；

• 因为链表的特殊性，扩展链表并不会带来额外的消耗；

• 考虑维护两个链表，分别保存小于 x 的节点和其他节点；最后将两个链表拼接即可；

• 此外还有一种基于双指针的思路：

  • 考虑左指针有右指针，开始时，直接将右指针移动到末尾，然后遍历左指针，遇到大于等于 x 的节点就移动到右指针的位置；

Python

# 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
        
        small = l = ListNode(0)
        large = r = ListNode(0)
        
        cur = head
        while cur:
            if cur.val < x:
                l.next = cur
                l = l.next
            else:
                r.next = cur
                r = r.next
            cur = cur.next
        
        l.next = large.next
        r.next = None
        return small.next