LeetCode刷题之旅（简单-7）：合并两个有序链表

LeetCode刷题之旅（简单-7）：合并两个有序链表

2019年5月13日

目录

​​题目：合并两个有序链表​​

​​解决方法一：使用辅助节点，指向联表末端元素​​

​​性能结果：​​

​​小结：​​

​​解决方法二：使用递归方法​​

​​性能结果：​​

​​思路：​​

​​小结：​​

前言：基础不好的童鞋，花点时间回顾下基础数据结构：链表

题目：合并两个有序链表

解决方法一：使用辅助节点，指向联表末端元素

package leetCode;/** * Date: 2019/5/8 12 :21 * * @todo 将两个有序链表合并为一个新的有序链表并返回。 */public class MergeTwoOrderedLists { public static void main(String[] args){ ListNode l1 = new ListNode(1); l1.next = new ListNode(2); l1.next.next= new ListNode(4); ListNode l2 = new ListNode(1); l2.next=new ListNode(3); l2.next.next= new ListNode(4); System.out.println("l1="+l1+" l2="+l2); ListNode l3 = mergeTwoLists(l1, l2); System.out.println("l3="+l3); } public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 1.l3取l1的首结点 ListNode head = new ListNode(0); ListNode cur = head; if(l1 == null){ return l2; } if (l2 == null){ return l1; } if (l1 != null && l2 != null){ // 2.l2或者l1的结点都不为空 while (l2 != null || l1 != null){ if (l1.val < l2.val){ cur.next = l1; //l1首元素地址赋值给cur指向的next元素 cur = cur.next; //cur也指向next元素 l1 = l1.next; }else { cur.next = l2; cur = cur.next; l2 = l2.next; } // 3.任意一条链表为空时，直接连接另外一条即可 if (l1 == null){ cur.next = l2; break; } if (l2 == null){ cur.next = l1; break; } } } return head.next; }}class ListNode { int val; ListNode next; ListNode(int x) { val = x; } public ListNode() { }};

性能结果：

小结：

链表保存的下一个节点信息，是下一个元素的内存首地址，为null时则是链表的最后一个元素；新建头结点，新建cur为位移指针，cur的作用是作为新建头结点的指针，不断给头结点进行元素补充；每个方法都要考虑充分的异常情况：比如某个链表为空，那就返回另外一个；比如两个输入链表的长度不一致，也要考虑；

解决方法二：使用递归方法

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null){ return l2; } if(l2==null){ return l1; } if(l1.val

性能结果：

思路：

1）迭代方法每次选两个链表头结点最小的，比如：我们生活中，有两个已经按照高矮排好的队伍，我们如何把变成一个队伍！当然，每次选两个队伍排头的，比较他们的高矮!组成新的的队伍。时间复杂度：O(m+n)O(m+n)空间复杂度：O(m+n)O(m+n)2）递归方法

小结：

从大脑反应程度看，确实灵敏了很多，自己也看到了进步，but，远远不够的，因为《数据结构与算法》一书，才刚刚开始看啊！没到登峰造极，剑不能收！努力。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。