共计 1198 个字符，预计需要花费 3 分钟才能阅读完成。
原文链接：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;
}
}
