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

bicycle_journey-wallpaper

原文链接：https://wangwei.one/posts/java-algoDS-Merge-Two-Sorted-Linked-Lists.html

前面，我们实现了链表的 环检测 操作，本篇来聊聊，如何合并两个有序链表。

有序链表合并

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;
    }
    
}

参考资料

• 《数据结构与算法之美》