【LeetCode】合并两个排序的链表 Java 题解
题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
复制代码
思路分析
这是一个链表题目,链表通过指针来连接元素,链表可以方便地删除、插入数据,时间复杂度都是 O(1)。
根据题意可得,l1, l2 都是递增的排序链表,利用这个特性,思路可以简化,直接迭代下一个节点,都是递增的。
在递归解法中,如果 l1 节点值比 l2 小,下一个节点应该是 l1,应该 return l1,在 return 之前,指定 l1 的下一个节点应该是 l1.next 和 l2 俩链表的合并后的头结点。同理可得 l1 节点值 大于 l2 的情况。
在迭代解法中,定义了哨兵节点,这可以在最后让我们比较容易地返回合并后的链表。这个操作解决链表问题很常见,请多学习一下这种解法。
通过代码
递归解法
复制代码
非递归解法
复制代码
总结
上述算法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/d22ba5356a3b4e7267e5c2c83】。文章转载请联系作者。
评论