86. 分隔链表(Medium)

题目描述

给定一个链表和一个特定值 x，要求重排链表，使得所有小于x 的点在大于x的点前面。节点的初始相对位置不变。

Leetcode 地址

解题思路

• 两个伪节点

代码

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        dummpyHead1 = ListNode(None)
        dummpyHead2 = ListNode(None)
        p1, p2 = dummpyHead1, dummpyHead2
        while head: # 因为 head 之后用不到，所以直接不客气拿来用
            if head.val < x:
                p1.next = head 
                p1 = p1.next 
            else:
                p2.next = head 
                p2 = p2.next
            head = head.next
        p1.next = dummpyHead2.next 
        p2.next = None  # 这一步注意，是为了避免死循环
        return dummpyHead1.next

func partition(head *ListNode, x int) *ListNode {
    dummpyHead := &ListNode{}
    dummpyHead2 := &ListNode{}
    p1, p2 := dummpyHead, dummpyHead2
    for head != nil {
        if head.Val < x {
            p1.Next = head
            p1 = p1.Next
        } else {
            p2.Next = head
            p2 = p2.Next
        }
        head = head.Next
    }
    p1.Next = dummpyHead2.Next
    p2.Next = nil // 非常重要，很容易忘记
    return dummpyHead.Next
}