No.021：Merge Two Sorted Lists-白红宇的个人博客

No.021：Merge Two Sorted Lists

发布日期：2021-05-09 03:59:00 浏览次数：10 分类：博客文章

本文共 1389 字，大约阅读时间需要 4 分钟。

问题：

Merge two sorted linked lists and return it as a new list.

The new list should be made by splicing together the nodes of the first two lists.

官方难度：

Easy

翻译：

合并2个已排序的链表，得到一个新的链表并且返回其第一个节点。

考虑输入节点存在null的情况，直接返回另一个节点。

节点的定义在No.002（Add Two Numbers）中有定义。

记录上一个节点last，保留第一个节点first。

以其中一条链表为基准，作为待排序的链表，其第一个节点记为l1。比较l1和l2的value值，如果l1的value是较大的一方，交换l1和l2节点，保证last节点的next指针指向l1节点。

当l1节点的next指针为null时，表明第一条链表完全有序，且最后一个节点的值小于另一条链表第一个节点的值，连接这两个节点，整条链表自然有序。

解题代码：

1     public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { 2         if (l1 == null) { 3             return l2; 4         } 5         if (l2 == null) { 6             return l1; 7         } 8         // 返回的第一个节点 9         ListNode first = l1.val > l2.val ? l2 : l1;10         // 上一个节点11         ListNode last = new ListNode(0);12         while (true) {13             if (l1.val > l2.val) {14                 // 交换l1节点和l2节点，保证下一次循环仍然以l1节点为基准15                 ListNode swapNode = l2;16                 l2 = l1;17                 l1 = swapNode;18             }19             // 将last节点的next指针指向l1，同时更新last20             last.next = l1;21             last = l1;22             // 带排序的链表遍历完成，剩余链表自然有序23             if (l1.next == null) {24                 l1.next = l2;25                 break;26             }27             l1 = l1.next;28         }29         return first;30     }

mergeTwoLists

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章