题目描述
✅ 面试题 02.04. 分割链表
思路分析
我们可以使用两个虚拟头节点来分别存储小于 x 的节点和大于或等于 x 的节点。遍历链表时，将节点根据值的大小分别添加到这两个链表中。最后，将小于 x 的链表与大于或等于 x 的链表连接起来。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
func partition(head *ListNode, x int) *ListNode {
if head == nil || head.Next == nil {
return head
}
leftHead, rightHead := &ListNode{}, &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
}
left.Next = rightHead.Next
right.Next = nil
return leftHead.Next
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func partition(head *ListNode, x int) *ListNode {
preHead := &ListNode{}
postHead := &ListNode{}
pre := preHead
post := postHead
for cur := head; cur != nil; cur = cur.Next {
if cur.Val < x {
pre.Next = cur
pre = pre.Next
} else {
post.Next = cur
post = post.Next
}
}
// 连接两个链表
pre.Next = postHead.Next
post.Next = nil // 断开后面的链表
return preHead.Next
}
|
➡️ 点击查看 Java 题解
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！