两个升序有序Java_【Java面试题】——— 合并两个有序链表（递归法、迭代法）...

题目描述：

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4

输出：1->1->2->3->4->4

方法一：迭代法

比较两个链表的头结点，将较小的节点作为合并后的新链表的头结点

初始状态：

第一次合并：

第二次合并：

第三次合并：

第四次合并：

代码实现：

class ListNode{

int val;

ListNode next;

public ListNode(int x){

x=val;

}

}

public class MergeOrderLinkedList {

public ListNode method1(ListNode l1,ListNode l2){

//new一个新的链表

//在返回节点之前维护对节点的不变引用。

ListNode res = new ListNode(-1);

ListNode prev = res;

//结束的条件是其中一个链表为空

while (l1!=null && l2!=null) {

//比较两个链表的头结点，较小的作为新链表的头结点

if (l1.val <= l2.val) {

prev.next = l1;

//将指针后移一位

l1 = l1.next;

}else{

prev.next = l2;

l2 = l2.next;

}

//新链表的指针也要向后移动一位

prev = prev.next;

}

//最后一步：当某个链表为空时，将另一个不为空的链表加入到新链表中

prev.next = l1 == null ? l2 : l1;

//返回新链表

return res.next;

}

}

方法二：递归

递推公式：

也就是说，比较两个链表的头结点，将头结点较小的那个链表的剩余部分，与另一个链表进行递归合并。

 

public ListNode method2(ListNode l1,ListNode l2){

//如果某一个链表为空，返回另一个不为空的链表

if(l1==null){

return l2;

}

if(l2==null){

return l1;

}

if(l1.val<=l2.val){

//如果list1的头结点小于list的头结点，递归 合并list1剩余的部分和list2

l1.next = method2(l1.next,l2);

return l1;

}else {

l2.next = method2(l2.next, l1);

return l2;

}

}