題目
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
解題思路
新建一個(gè)鏈表l3竭缝，遍歷l1,l2, 每次比較l1,l2中第一個(gè)節(jié)點(diǎn)大小，選擇較小的元素放入l3的末尾
- 先找到l1,l2中第一個(gè)較小的元素，作為l3第一個(gè)元素
- 遍歷l1,l2括授，將其中元素插入l3末尾婶博，直到l1践瓷，l2中有一個(gè)鏈表遍歷完
- 如果l1為空分衫，則將l2剩余元素放到l3末尾据德；如果l2為空减拭，則將l1剩余元素放到l3末尾
代碼
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if nil == l1 {
return l2
}
if nil == l2 {
return l1
}
var p3 *ListNode
p1, p2 := l1, l2
if p1.Val < p2.Val {
p3 = p1
p1 = p1.Next
p3.Next = nil
} else {
p3 = p2
p2 = p2.Next
p3.Next = nil
}
l3 := p3
for ;p1 != nil && p2 != nil; {
if p1.Val < p2.Val {
tmp := p1
p1 = p1.Next
p3.Next = tmp
p3 = p3.Next
p3.Next = nil
} else {
tmp := p2
p2 = p2.Next
p3.Next = tmp
p3 = p3.Next
p3.Next = nil
}
}
if p1 != nil {
p3.Next = p1
} else {
p3.Next = p2
}
return l3
}
