【java容器的刻意练习】【十二】LinkedList的笔试题

这篇看看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;

多多学习别人的思路，收益会非常大。