目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
21-合并两个有序链表
访问量:2313
一、题目
题目地址:
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
二、解法
1、解法1
思路:队列l1,l2,因为都是有序排列,所以,只需要,把l1作为基队列,将l2拼接到l1上面。
/* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类 */ func Merge( pHead1 *ListNode , pHead2 *ListNode ) *ListNode { // write code here if pHead1 == nil { return pHead2 } if pHead2 == nil { return pHead1 } // 以pHead1为基准链表,保证最小值在 pHead1 if pHead1.Val > pHead2.Val { pHead1, pHead2= pHead2, pHead1 } tmp := pHead1 for pHead2 != nil { if tmp.Next == nil { tmp.Next = pHead2 return pHead1 } else if pHead2.Val < tmp.Next.Val { // 将 p2从当前节点移除 node2 := pHead2 pHead2 = pHead2.Next // 将 p2节点插入 p2链表中 node2.Next = tmp.Next tmp.Next = node2 // 将p2 移动 tmp = node2 } else { tmp = tmp.Next } } return pHead1 }
2、递归版本
func Merge( pHead1 *ListNode , pHead2 *ListNode ) *ListNode { // write code here if pHead1 == nil { return pHead2 } if pHead2 == nil { return pHead1 } if pHead1.Val < pHead2.Val { pHead1.Next = Merge(pHead1.Next, pHead2) return pHead1 } else { pHead2.Next = Merge(pHead2.Next, pHead1) return pHead2 } }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助