合并链表模板

目录

[toc]

按大小合并

    private ListNode merge(ListNode node1, ListNode node2) {
        if (node1 == null) { return node2; }
        if (node2 == null) { return node1; }
        // 创建哨兵
        ListNode sentinel = new ListNode(-1);
        ListNode curr = sentinel;
        // 合并过程
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                curr.next = node1;
                node1 = node1.next;
            } else {
                curr.next = node2;
                node2 = node2.next;
            }
            curr = curr.next;
        }
        // 其中一个链表到达末尾
        if (node1 != null) { curr.next = node1; }
        else if (node2 != null) { curr.next = node2; }
        return sentinel.next;
    }

按顺序合并

一个 L1 一个 L2 按顺序合并

    private void merge(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;
 
            l1.next = l2;
            l1 = l1_tmp;
 
            l2.next = l1;
            l2 = l2_tmp;
        }
    }