【LeetCode21】合并两个有序链表(循环 + 递归)
题目描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
提交结果:
循环解法(类似归并排序的merge过程)
核心思想:
-
创建一个新的头节点作为合并后的链表
dummyHead
。 -
定义两个指针
cur1,cur2
,分别指向链表1和链表2的头节点,然后比较cur1.val
和cur2.val
将值小的结点挂在新的链表上然后让相应的cur后移,值大的结点的cur指针保持不动。循环该过程,直至一个链表已经遍历完毕。 -
判断哪个链表还没有遍历完毕,然后将该链表的剩余结点全部挂在新返回链表上即可。
注:因为每一次都只有一个链表的cur指针后移,因此最终必有一个链表没有遍历完毕。
代码实现:
public class MergeTwoList {
public static ListNode mergeTwoLst(ListNode head1,ListNode head2){
// 处理异常情况
if(head1 == null) return head1;
if(head2 == null) return head1;
// 新链表的dummyHead,初始值随意
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
ListNode cur1 = head1;
ListNode cur2 = head2;
// 遍历
while(cur1 != null && cur2 != null){
if(cur1.val <= cur2.val){
cur.next = cur1;
cur1 = cur1.next;
}else{ // cur1.val > cur2.val
cur.next = cur2;
cur2 = cur2.next;
}
cur = cur.next;
}
// 一个链表已经遍历完毕
if(cur1 != null){
cur.next = cur1;
}else{
cur.next = cur2;
}
return dummyHead.next;
}
}
递归解法
主体思想和循环一样,只是在我们将第一个结点挂到新的头节点之后,仍然处理的是合并两个有序链表的问题,只是其中一个链表的规模减少了一个结点而言,因此是原问题的子过程,我们可以继续调用该方法处理子问题。
代码实现:
public static ListNode mergeTwoLstR(ListNode head1,ListNode head2){
if(head1 == null) return head2;
if(head2 == null) return head1;
ListNode newHead = null;
if(head1.val <= head2.val){
newHead = head1;
newHead.next = mergeTwoLst(head1.next,head2);
}else{
newHead = head2;
newHead.next = mergeTwoLst(head1,head2.next);
}
return newHead;
}
}