Merge Two Sorted List

解法一: 迭代

通过遍历两个链表，比较两者的元素来完成 merge，对于最后剩下的链表，直接把元素添加到链表末尾即可。

/*
 * 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 head = new ListNode(-1); // 任意定义一个表头
        ListNode prev = head; // 定义一个指针，从 head 开始
        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 head.next;
    }
}

时间复杂度 O(m + n), 空间复杂度 O(1)

解法二: 递归

？？？

本作品采用《CC 协议》，转载必须注明作者和本文链接