1.1. 题目
1.1.1. 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
1.1.2. 题解:
- 链表是有序的
- 合并后的还是一个有序的链表
1.1.3. 思路:
- 走偏门(作弊):比如把链表数据都遍历放到一个数组里,然后把数据排序,再组成一个新的链表
- 正常思路: 两个链表各一个指针移动,从头开始遍历,谁小谁放入到合并后的链表里,然后小的那个指针移动到下一个
- 比如示例里,先比如 A链表(1->2->4)的1和B链表(1->3->4)的1进行比较,不用考虑相等的情况,当相等的时候,可以默认取第一个,那么A的1放入到新链表,A指针往后移动
- 然后用A链表的2跟B链表的1进行比较,B链表的1比较小,然后把B链表的1放入到合并后的链表,B链表指针往后移动
- 如果有一个指针移动到了末尾,如果此刻两个链表都指向了nil,那么直接返回合并后的链表的头节点
- 如果还有一个链表没有走到头,那么把剩下的数据放到合并的数据末尾就可以了!毕竟都是有序的
1.1.4. 代码:
点击显示
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
newNode := &ListNode{Val:0}
head := newNode
for l1 != nil && l2 != nil {
if l1.Val > l2.Val {
newNode.Next = l2
l2 = l2.Next
} else {
newNode.Next = l1
l1 = l1.Next
}
newNode = newNode.Next
}
if l1 != nil {
newNode.Next = l1
}
if l2 != nil {
newNode.Next = l2
}
return head.Next
}