写点什么

合并两个有序链表

作者:田镇珲
  • 2021 年 12 月 29 日
  • 本文字数:1190 字

    阅读完需:约 4 分钟

合并两个有序链表

leetcod

思路

  1. 新建一个链表来存储结果

  2. 用两个指针分别指向两个链表最开头的那两个节点

  3. 对比两个节点, 如果把值小的放入结果链表中,并且向后移一个节点

  4. 直到一条链表移到末尾的下一个(也就是空)

  5. 考虑并处理两个空链表的情况


那么, 大概思路有了, 就是具体实现了。 具体实现的时候, 我们要考虑几方面

如何初始化, 以及更新存储结果那个链表。

一个链表我们需要返回的就是一个节点 node, 一般我们新建一个节点。

那么这个节点又该怎么赋值呢?

其实这个节点最重要的地方是 hold 住这个链表, 相当于我们要抓住这个头, 就像我们抓取一个铁链, 肯定不会说是抓住全部铁链那个环。 单向链表和铁链不一样的地方在于, 如果你抓住一个铁环, 是拎不起来前面的铁环的, 只能拎起来后面的铁环。所以我们需要这个头环, 当我们组织好这条铁链过后, 再抓住这个头环的下一个环, 就是我们需要的环了。

我们如何更新呢?

用两个指针, 一个指着头(一般 new 一个特殊值节点 -1), 一个用来向后不断前进.

在更新的时候又是如何保证链不断呢?

这有一个演绎的概念,


  1. 保证开头是对的,

  2. 上一个和下一个的关系是对的,那么我的整个链条就是对的。回到链表。 保证开头是对的, 也就是说, 我需要有一个指针来指向开头的那个节点。保证上一个和下一个的关系是对的, 也就是说, 我使用另一个指针来操作这个节点的时候,需要保证, 1, 当前这个节点的 next 被赋值过后, 才将这个指针移到下一个节点。


ListNode a = new ListNode(-1);ListNode p = a;p.next = nexListNode;p = p.next;
复制代码

在进行比较的 while 循环的判断条件, 是使用当前点还是 next 点

主要看你在循环体内对比值是对比的那个节点的值, 如果你对比的是当前节点的值, 却用 next 是否为空来判断结束条件, 就会有最后一个节点没法做对比。

代码

/**
* 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 list1, ListNode list2) {
ListNode point1 = list1;
ListNode point2 = list2;
ListNode head = new ListNode(-1);
ListNode p = head;

if (point1 == null && point2 == null) {
return null;
}
while (point1 != null && point2 != null) {
if (point1.val < point2.val) {
p.next = point1;
point1 = point1.next;
}
else {
p.next = point2;
point2 = point2.next;
}
p = p.next;
}

// 拼接剩下的
if (point2 != null) {
p.next = point2;
}
if (point1 != null) {
p.next = point1;
}

// 去掉临时头
head = head.next;

return head;
}
}
复制代码


用户头像

田镇珲

关注

还未添加个人签名 2019.11.29 加入

还未添加个人简介

评论

发布
暂无评论
合并两个有序链表