Merge Two Sorted Lists
https://leetcode.com/problems/merge-two-sorted-lists/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
p := dummy
p1 := list1
p2 := list2
for p1 != nil && p2 != nil {
if p1.Val < p2.Val {
p.Next = p1
p1 = p1.Next
p = p.Next
} else {
p.Next = p2
p2 = p2.Next
p = p.Next
}
}
for p1 != nil {
p.Next = p1
p1 = p1.Next
p = p.Next
}
for p2 != nil {
p.Next = p2
p2 = p2.Next
p = p.Next
}
return dummy.Next
}
优化解法
最后去合并剩余的 list1 / list2 时，不需要逐节点合并，只需要让 p.Next 指向最终剩余的 list 即可（其他节点已经「组成好一个有序链表」了）
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
p := dummy
p1 := list1
p2 := list2
for p1 != nil && p2 != nil {
if p1.Val < p2.Val {
p.Next = p1
p1 = p1.Next
p = p.Next
} else {
p.Next = p2
p2 = p2.Next
p = p.Next
}
}
if p1 != nil {
p.Next = p1
}
if p2 != nil {
p.Next = p2
}
return dummy.Next
}
Partition List
https://leetcode.com/problems/partition-list/
题意：看上去返回的是一个链表，实际上是返回了两个链表连起来的。。
相当于生成两个新的链表，一个链表的所有值都 < x，另一个都 >=x ，再将这两个链表合到一起
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
dummy1 := &ListNode{}
dummy2 := &ListNode{}
p1 := dummy1
p2 := dummy2
for p := head; p != nil; p = p.Next {
if p.Val < x {
p1.Next = p
p1 = p1.Next
} else {
p2.Next = p
p2 = p2.Next
}
}
p1.Next = dummy2.Next
p2.Next = nil
return dummy1.Next
}