共计 469 个字符,预计需要花费 2 分钟才能阅读完成。
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;
}
}
正文完