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
}