leetcode:21.合并两个有序链表

蔚落 2022-04-23 16:10 344阅读 0赞

题目描述：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
  1. 输入：1->2->4, 1->3->4
  2. 输出：1->1->2->3->4->4
题目难度：简单
分析：

easy级别的题目，熟悉链表的话很快就可以做出来，只需要定义一个空节点，然后利用递归去找到l1和l2中值较小的节点，然后作为这个空节点的next节点即可，这样最后返回的这个空节点就是从小到大排序的链表了。
代码如下：

  1. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
  2. class Solution { 
  3.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
  4.         // 如果两个链表有一个为null，那么返回另一个即可
  5.         if (l1 == null) { 
  6.             return l2;
  7.         }
  8.         if (l2 == null) { 
  9.             return l1;
  10.         }
  11.         // 利用递归，找到l1和l2中较小值的节点，并作为resNode的next节点即可
  12.         ListNode resNode;
  13.         if (l1.val < l2.val) { 
  14.             resNode = l1;
  15.             resNode.next = mergeTwoLists(l1.next, l2);
  16.         } else { 
  17.             resNode = l2;
  18.             resNode.next = mergeTwoLists(l1, l2.next);
  19.         }
  20.         return resNode;
  21.     }
  22. }
总结：

时间复杂度为 O ( m a x ( m , n ) ) O(max(m, n)) O(max(m,n))，需要递归去操作两个链表，m、n为两个链表的长度。

发表评论

表情：
评论列表 （有 0 条评论，344人围观）

还没有评论，来说两句吧...

相关阅读