首页 > 代码库 > [leetcode]Merge Two Sorted Lists

[leetcode]Merge Two Sorted Lists

2024-07-12 22:35:58   222人阅读

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.

算法思路：

以l1为基准，拿l2的点逐个插入到l1中，两个链表都是一次遍历，我这里没有做优化，时间复杂度O(m+n)，空间复杂度O(1)

 

 1 public class Solution { 2     public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 3         if(l1 == null) return l2; 4         if(l2 == null) return l1; 5         ListNode head = new ListNode(1); 6         head.next = l1; 7         ListNode pre = head; 8         ListNode node = l2; 9         while(l2 != null){10             node = l2;11             while(pre.next != null && pre.next.val <= node.val){12                 pre = pre.next;13             }14             l2 = node.next;15             node.next = pre.next;16             pre.next = node;17             pre = node;//如果这句删掉的话，相当于l2扫描了两边，l1扫描一遍，但是时间复杂度不变18         }19         return head.next;20     }21 }


联系
我们