这篇看看leetcode的 [21]合并2个有序链表：
//将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//
// 示例：
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
//
// Related Topics 链表
//leetcode submit region begin(Prohibit modification and deletion)
还记得我们在《【五】ArrayList考点》里面做过的第905题按奇偶排序数组吗？我们用来2个引用，快慢引用或者左右引用，对一个数组进行遍历并进行元素换位。
这一题我们能不能用这样的思路去做呢？
- 同时遍历这2个链表，对当前2个元素进行大小比较。
- 较小元素的节点就“摘”出来，放到输出链表里面。
- 当某个链表已经遍历完，把另外链表多余的元素直接接到输出链表后面即可
这样我们只需要O(n+m)的时间复杂度，而且不需要额外的空间。
/**
* 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) {
// 输出链表的头引用
ListNode head = null;
// 输出链表的尾引用
ListNode tail = null;
// 用于摘取节点后继续定位下一个节点
ListNode temp = null;
// 用于2个元素比较后，引用较小的节点
ListNode min = null;
while (l1 != null || l2 != null) {
// 特殊情况，考虑 l1先结束，把 l2 剩余的也连接到输出链表的尾部
if (l1 == null && l2 != null) {
if (tail != null) {
tail.next = l2;
} else {
tail = l2;
head = tail;
}
break;
}
// 特殊情况，考虑 l2先结束，把 l1 剩余的也连接到输出链表的尾部
if (l1 != null && l2 == null) {
if (tail != null) {
tail.next = l1;
} else {
tail = l1;
head = tail;
}
break;
}
// 先把最小的一个拿出来
if (l1.val > l2.val) {
temp = l2.next;
min = l2;
l2 = temp;
} else {
temp = l1.next;
min = l1;
l1 = temp;
}
// 第一次设置head
if (null == head && null == tail) {
head = min;
tail = head;
}
// 尾部添加节点，尾巴往后移动
if (tail != min) {
tail.next = min;
tail = min;
}
}
return head;
}
}
写完了，先提交看看。
第一次提交
还不错，拿了双百。
然后，我们再看看其他优秀答案是怎样的。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// maintain an unchanging reference to node ahead of the return node.
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// exactly one of l1 and l2 can be non-null at this point, so connect
// the non-null list to the end of the merged list.
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
居然如此简短！！！
我们看看究竟跟我们想法有什么不同？
// maintain an unchanging reference to node ahead of the return node.
ListNode prehead = new ListNode(-1);
...
return prehead.next;
原来精妙之处在这里！！！
虚构了一个链表头！！！（这个元素值无所谓，-1也好，0也好，1000也好，都无所谓。）通过这个链表头，就可以节省很多链表头的初始化代码！返回的时候只需要从这个虚拟节点后面开始返回即可！！！
还有这里，循环到任意链表结束就立马结束，然后用来三元运算符，判断是否存在已经遍历结束的链表，大大缩减了剩余节点的判断代码：
while (l1 != null && l2 != null)
...
// exactly one of l1 and l2 can be non-null at this point, so connect
// the non-null list to the end of the merged list.
prev.next = l1 == null ? l2 : l1;
多多学习别人的思路，收益会非常大。
网友评论