LeetCode 面试题 02.04. 分割链表

题目描述

🔥 面试题 02.04. 分割链表

思路分析

解题思路：

  1. 创建两个链表 beforeHead 和 afterHead，分别用于存储小于 x 的节点和大于等于 x 的节点。
  2. 遍历原链表，将节点根据其值分别连接到 beforeHead 和 afterHead。
  3. 最后，将 beforeHead 的尾节点与 afterHead 的头节点相连接，并返回 beforeHead 的头节点作为结果。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2023/89866580
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！