LeetCode 86. 分隔链表

Categories:

题目描述
思路分析
参考代码

题目描述

🔥 86. 分隔链表

思路分析

解题思路：

创建两个链表 beforeHead 和 afterHead，分别用于存储小于 x 的节点和大于等于 x 的节点。

遍历原链表，将节点根据其值分别连接到 beforeHead 和 afterHead。

最后，将 beforeHead 的尾节点与 afterHead 的头节点相连接，并返回 beforeHead 的头节点作为结果。

参考代码

func partition(head *ListNode, x int) *ListNode {
	leftHead := &ListNode{}
	rightHead := &ListNode{}
	left, right := leftHead, rightHead
	cur := head
	for cur != nil {
		if cur.Val < x {
			left.Next = cur
			left = left.Next
		} else {
			right.Next = cur
			right = right.Next
		}
		cur = cur.Next
	}
	right.Next = nil // 特别注意：此处一定要断开，防止循环引用。
	left.Next = rightHead.Next
	return leftHead.Next
}

func partition(head *ListNode, x int) *ListNode {
	beforeHead := &ListNode{} // 虚拟头节点，用于存储小于 x 的节点
	afterHead := &ListNode{}  // 虚拟头节点，用于存储大于等于 x 的节点
	before := beforeHead
	after := afterHead

	cur := head

	for cur != nil {
		if cur.Val < x {
			before.Next = cur
			before = before.Next
		} else {
			after.Next = cur
			after = after.Next
		}
		cur = cur.Next
	}

	// 连接 before 和 after 部分
	after.Next = nil
	before.Next = afterHead.Next
	return beforeHead.Next
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/63245444