JAVA练习295- 合并两个有序链表

题目概览将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]示例 2输入l1 [], l2 []输出[]示例 3输入l1 [], l2 [0]输出[0]提示两个链表的节点数目范围是[0, 50]-100 Node.val 100l1和l2均按非递减顺序排列来源21. 合并两个有序链表 - 力扣LeetCode解题分析方法一迭代同时遍历两个链表比较两个节点小的节点放在合并链表里然后小节点往后遍历直到一个链表遍历完成拼上另一个没遍历完的链表即可。时间复杂度O(n)空间复杂度O(1)/** * 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) { ListNode a list1, b list2; ListNode temp new ListNode(); ListNode result temp; while(true) { if (a null) { temp.next b; break; } if (b null) { temp.next a; break; } if (a.val b.val) { temp.next b; b b.next; } else { temp.next a; a a.next; } temp temp.next; } return result.next; } }方法二递归合并本质上就是把修改两个链表中较小的节点的指针让它指向第二小的因此我们可以用递归的方式让当前方法返回最小的节点最小的节点指向第二小的节点最小节点的下个节点和另一个节点的比较结果 即 再调用当前方法。时间复杂度O(n)空间复杂度O(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; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 null) { return list2; } if (list2 null) { return list1; } if (list1.val list2.val) { list2.next mergeTwoLists(list1, list2.next); return list2; } list1.next mergeTwoLists(list1.next, list2); return list1; } }