java怎么合并兩個有序鏈表

134次閱讀

共計 933 個字符，預計需要花費 3 分鐘才能閱讀完成。

可以使用遞歸的方式來合并兩個有序鏈表。具體步驟如下：

判斷兩個鏈表中是否存在為空的情況，若其中一個鏈表為空，則直接返回另一個鏈表。
比較兩個鏈表頭結點的值，將值較小的頭結點作為合并后的鏈表的頭結點。
將較小頭結點的 next 指針指向遞歸調用合并后的鏈表。
返回合并后的鏈表的頭結點。

以下是一個示例的 Java 代碼實現：

class ListNode {int val;
    ListNode next;
    
    ListNode(int val) {this.val = val;
    }
}

public class Solution {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;
        }
    }
}

使用示例：

public class Main {public static void main(String[] args) {// 創建兩個有序鏈表 
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);
        
        // 合并兩個有序鏈表 
        Solution solution = new Solution();
        ListNode mergedList = solution.mergeTwoLists(l1, l2);
        
        // 打印合并后的鏈表 
        while (mergedList != null) {System.out.print(mergedList.val + " ");
            mergedList = mergedList.next;
        }
    }
}