21.合并兩個有序連結清單Java

題目描述

将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。

輸入輸出樣式

示例1：

輸入：l1 = [1,2,4], l2 = [1,3,4]

輸出：[1,1,2,3,4,4]

示例2：

輸入：l1 = [], l2 = [0]

輸出：[0]

本文題來自LeetCode：https://leetcode-cn.com/problems/merge-two-sorted-lists/

思路

方法一：疊代的方法，即依次比較l1和l2連結清單節點的大小，将較小的添加到要傳回的新連結清單中，同時已經被添加的連結清單節點指針往後移動一位。

方法二：遞歸。主要思想：兩個連結清單頭部值較小的節點和剩下的元素遞歸合并。

算法分析

1. 疊代：時間複雜度為O(n + m)，其中m，n為連結清單的長度，空間複雜度為O(1)。
2. 遞歸：時間複雜度O(m + n），其中m，n為連結清單的長度；空間複雜度為O(m + n)，遞歸需要調用棧，最多調用m+n次。

求解函數

//方法一：疊代
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode nLinkList = new ListNode();
        ListNode p1 = l1, p2 = l2, p = nLinkList; //p1,p2為連結清單指針
        while (p1 != null && p2 != null) {
            if (p1.val > p2.val) { //插入較小的節點
                p.next = p2;
                p = p.next;
                p2 = p2.next;
            } else {
                p.next = p1;
                p = p.next;
                p1 = p1.next;
            }
        }
        if (p1 == null && p2 == null) return nLinkList.next;
        else if (p1 == null) { //如果p1為空，p2不空則一次插入p2剩下節點
            while (p2 != null) {
                p.next = p2;
                p = p.next;
                p2 = p2.next;
            }
        } else { //如果p2為空，p1不空則一次插入p1剩下節點
            while (p1 != null) {
                p.next = p1;
                p = p.next;
                p1 = p1.next;
            }
        }
        return nLinkList.next; //傳回next因為頭結點沒用
    }
           

//方法二：遞歸 
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }