2020/10/15合并两个有序链表
2020-10-15 本文已影响0人
小mg
leetCode题目-合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
代码样式
/**
* 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 l1, ListNode l2) {
}
}
我的代码，思路极其繁琐，同时还没有完全实现功能
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
List<Integer> list=new ArrayList<Integer>();
do{
list.add(l1.val);
l1=l1.next;
if (l1.next==null) list.add(l1.val);
}while(l1.next!=null);
do{
list.add(l2.val);
l2=l2.next;
if (l2.next==null) list.add(l2.val);
}while(l2.next!=null);
Collections.sort(list);
System.out.println(list);
ListNode head= new ListNode(0);
ListNode currt=head;
for(int i=0;i<list.size();i++){
currt.next=new ListNode(list.get(i));
currt=currt.next;
}
return head.next;
}
思路
l1=l1.next;
if (l1.next==null) list.add(l1.val);
- 首先是将两个单向链表的值全部取出放到一个list集合中，但此时就出现了问题，就是在上面这句中,首先对链表l1进行了指向下一个节点的操作，然后在之后的if判断语句中再进行l1.next的判断，就相当于对最初的 l1进行 l1.next.next的判断，极其容易报NullPointException;
- 然后就是使用list集合的排序方法 Collections.sort(list); 对集合进行排序
- 最后再将排序好的集合遍历放到一个链表中
ListNode head= new ListNode(0);
ListNode currt=head;
这里有个需要注意的问题,就是下面两行代码，不能直接写成ListNode currt= new ListNode(0);因为后面是对currt进行操作，在算法结束之后，不再指向头节点，所以一开始需要一个虚拟头节点保留对链表头节点的引用（在下面的简单实现中也是）
解法一：java简单实现
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 类似归并排序中的合并过程
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
// 任一为空，直接连接另一条链表
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummyHead.next;
}
思路
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
- 首先这里和上面一样，都是得创建一个虚拟节点指向头引用
- 其次这里的cur.next指向的是 l1.val和 l2.val比较后较小的那个链表，被cur.next指向的较小的链表需要再指向自己的下一个节点.next，cur也指向自己的下一个几点存放之后两个链表比较，值小的那一个链表。
- 然后只要 l1 != null && l2 != null就一直对后面的 l1.val和l2.val值进行比较
- 当 l1 l2中只要有一个出现null了之后就会跳出循环，直接将不为null的那个链表加到cur链表的尾部
- 最后输出要注意，因为dummyHead指向的是虚拟头节点，不是直接指向要输出的链表的头节点，指向的是要输出的链表的头节点的前一个节点。
解法二：递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
来源：力扣（LeetCode）
思路
和解法一的大体思路一样
- 对于 l1和 l2是否为null的判断是在开始和进行中都会执行的
- 递归的方法不是在新的链表后面进行改变，就是在原有的 l1 l2链表的基础上取最小的进行叠加，结束的条件是 l1或 l2有一个出现了null
单向链表的总结
链表结构图
- 单向链表和数组的对比，链表对于元素的查找不像数组一样可以通过下标快速定位，需要从头开始一个一个的遍历，直到取到元素，但是链表相对于数组的优点是，数组需要一块连续的内存空间，而链表不需要。
- 链表的结构是由数据和下一个节点的地址所组成的
- 对于链表的增删改查都需要结合节点中的地址来实现，改变节点地址的指向，来改变链表的结构
链表知识点链接 链表
