题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
示例1
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例2
输入：l1 = [], l2 = []
输出：[]
示例3
输入：l1 = [], l2 = [0]
输出：[0]
提示
/** * 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; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1==null){ return list2; } else if(list2==null){ return list1; } else if(list2.val > list1.val){ list1.next = mergeTwoLists(list1.next,list2); return list1; } else{ list2.next = mergeTwoLists(list1,list2.next); return list2; } } }
详细解读
这段代码实现了合并两个升序链表的算法。让我们逐步解读：
- 首先，创建一个名为dummy的虚拟头结点（dummy node），其值为0。这个dummy节点的作用是为了简化算法的实现，它的下一个节点将指向合并后的链表的头结点。
- 创建一个名为current的指针，初始化为dummy节点，用于迭代合并后的链表。
- 在一个while循环中，不断比较两个链表当前节点的值，选取其中较小的节点添加到合并后的链表中。循环的条件是两个链表都不为空。
- 如果l1的值小于l2的值，则将current的下一个节点指向l1，并将l1指针向后移动一位；否则将current的下一个节点指向l2，并将l2指针向后移动一位。
- 不断迭代直到其中一个链表到达末尾。
- 最后，如果其中一个链表还有剩余的节点，则直接将剩余链表接在合并后链表的末尾。
- 返回dummy节点的下一个节点，即合并后链表的头结点。
这个算法的时间复杂度是O(m + n)，其中m和n分别是两个输入链表的长度，因为它只需遍历每个节点一次。
idea上代码运行
class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } public class MergeTwoSortedLists { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { current.next = l1; l1 = l1.next; } else { current.next = l2; l2 = l2.next; } current = current.next; } if (l1 != null) { current.next = l1; } if (l2 != null) { current.next = l2; } return dummy.next; } public static void main(String[] args) { // Example usage: ListNode l1 = new ListNode(1); l1.next = new ListNode(3); l1.next.next = new ListNode(5); ListNode l2 = new ListNode(2); l2.next = new ListNode(4); l2.next.next = new ListNode(6); MergeTwoSortedLists merger = new MergeTwoSortedLists(); ListNode merged = merger.mergeTwoLists(l1, l2); // Print the merged list while (merged != null) { System.out.print(merged.val + " "); merged = merged.next; } } }
