Merge Two Sorted Lists 有序連結清單合并問題

Merge Two Sorted Lists 連結清單合并問題

題目

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

（源于Leetcode 第21 題）

給出的資料結構

public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }
           

解析

本題本質上就是連結清單合并問題。而且本題提供的是已經有序的單連結清單，是以不用進行預先操作。下面提供兩種解法

解法一

可以使用最普通的解法，就變将兩個連結清單的的元素一一對比進行合并，為此我們需要設定兩個周遊指針，一邊對比一遍周遊。當兩個連結清單長度不一緻的時候，周遊完後将剩餘的連結清單放置到目标連結清單的後面即可。時間複雜度為O(2n)

下面提供java代碼：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //若其中一個連結清單為空，直接傳回另外一個
        if(l1 == null){
            return l2;
        }
        if (l2 == null){
            return l1;
        }
        //p1，p2分别為l1，l2的周遊指針，l3為目标連結清單
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode l3 = null;
        //l3的初始化，取兩個連結清單的最小頭
        if(p1.val <= p2.val){
            l3 = p1;
            p1 = p1.next;
        }else{
            l3 = p2;
            p2 = p2.next;
        }
        //p3為l3的周遊指針
        ListNode p3 = l3;
        //逐個對比
        while(p1 != null && p2 != null){
            if(p1.val <= p2.val){
                p3.next = p1;
                p3 = p3.next;
                p1 = p1.next;
            } else{
                p3.next = p2;
                p3 = p3.next;
                p2 = p2.next;
            }
        }
        if(p1 != null){
            p3.next = p1;
        }
        if(p2 != null){
            p3.next = p2;
        }
        
        return l3;
    }
}
           

解法二

我們可以使用遞歸算法來完成。假設長為m，n的連結清單，若m頭結點的值比n頭結點的值要下，則接下來就是對比連結清單m.next和n了。反之毅然。

下面提供java代碼

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