数据结构与算法 | Leetcode 21:Merge Two Sorted Lists

原文链接：https://wangwei.one/posts/jav…

前面，我们实现了链表的 环检测 操作，本篇来聊聊，如何合并两个有序链表。
有序链表合并
Leetcode 21:Merge Two Sorted Lists
示例
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
使用虚假的Head节点
定义一个临时虚假的Head节点，再创建一个指向tail的指针，以便于在尾部添加节点。
对ListNode1和ListNode2同时进行遍历，比较每次取出来的节点大小，并绑定到前面tail指针上去，直到最终所有的元素全部遍历完。
最后，返回 dummyNode.next ，即为新链表的head节点。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyNode = new ListNode(0);
ListNode tail = dummyNode;

while(true){

if(l1 == null){
tail.next = l2;
break;
}

if(l2 == null){
tail.next = l1;
break;
}

ListNode next1 = l1;
ListNode next2 = l2;

if(next1.val <= next2.val){
tail.next = next1;
l1 = l1.next;
}else{
tail.next = next2;
l2 = l2.next;
}

tail = tail.next;
}

return dummyNode.next;

}

}
递归
使用递归的方式，代码比遍历看上去简洁很多，但是它所占用的栈空间会随着链表节点数量的增加而增加。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode result = null;

if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}

if(l1.val <= l2.val){
result = l1;
result.next = mergeTwoLists(l1.next, l2);
}else{
result = l2;
result.next = mergeTwoLists(l1, l2.next);
}
return result;
}

}