25. 合并两个排序的链表,双指针,递归
文章目录
25. 合并两个排序的链表

思路一:指针顺序遍历
头节点未知,就新建一个头指针,ListNode list = new ListNode(0);
谁小,head的next指针就指向谁
直到某一个链表空了,就让head接上另一个链表的剩余;
操作:
思路二:递归
终止条件:l1 l2其中一个为空时,返回另一个;
注意!!其中一个为空!的反 是 两个都不为空,
(l1!=null)&&(l2!=null)递归主体:
l1 = marge(l1.next,l2);
或
l2 = marge(l1,l2.next);下面以
l1 = [1,3,5]
l2 = [1,2,8,9]为例
递归进入,
空
操作:
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论