阿里面试题: 将两个升序链表合并成一个升序链表_合并链表为一个升序链表

题目

        将两个升序链表合并，合并后还是一个升序列表，尽量用最小的时间复杂度。

思路一

        两个链表合成一个链表，可以将两个链表打散，然后按照大小顺序放入到一个数组里，冒泡排序后，将节点串起来，这样就可以实现一个升序链表。

思路二

        思路一方法虽然可行，但是时间复杂度大于O(N2), 还重新创建了一个新数组去装这些元素, 空间复杂度也是比较大，因此方案一不可取。

        我们可以利用两个升序链表的特点: 可以按照顺序进行遍历，具体实现步骤如下:

        1)  定义一个新链表的头节点为两个链表中头节点的最小值。

 Node root=Max(l1.head.data,l2.head.data)

        2) 将剩下的两个链表，按照头头比较的规则，将值小的节点接入到新链表的尾节点, 因为每次我们就是取两个值，这两个值中肯定较小值肯定比新链表的尾节点的值要大，因此可以采用递归的思想来实现。

什么是头头比较?

        我们每次拿出两个链表的头节点，值小的节点插入到新链表尾，然后在旧链表中删除该节点。

        3) 递归结束的条件。 当任意一个链表结束时，也就意味着遍历结束和递归结束。如果是刚好比较完，那么就返回NULL插入到新链表的尾部，如果有一个链表遍历完了，另外一个链表还多余了很多节点，那么就直接将剩余的节点插入到新链表的尾部即可，因为每次递归(比较完毕后)旧链表中剩下的值总是大于或等于新链表的最大值。
 

import chain.ReverseList;
 
/**
 * @decription:
 * @date: 2021/7/9 10:50
 * 将两个升序链表合并，合并后还是一个升序列表，尽量用最小的时间复杂度。
 * 1->3-5>7
 * 2->4->5->8
 * 2  3  3 4
 * 1 1 2 3
 */
public class LinkedListMerge {
 
    static Node one;
 
    static Node two;
 
    static {
        one = new Node(1, new Node(3, new Node(5, new Node(7, null))));
        two = new Node(2, new Node(4, new Node(5, new Node(8, new Node(9, null)))));
    }
 
    static class Node {
        Integer data;
        Node next;
 
        public Node(Integer data, Node next) {
            this.data = data;
            this.next = next;
        }
 
        public Integer getData() {
            return data;
        }
 
        public void setData(Integer data) {
            this.data = data;
        }
 
        // 使用递归的思想遍历链表
        public String traverse() {
            return this.getData() + "->" + (this.next == null ? "NULL" : this.next.traverse());
        }
    }
 
 
    /**
     *  定义好头节点后，因为两个链表都是升序的，我们可以把每次的操作分解为三步:  比较两个链表的头节点 ->  将小的节点插入到新链表的尾节点-> 旧链表的节点移除。
     *  递归结束的条件: 任意一个链表为空链表。
     * @param l1
     * @param l2
     * @param node
     * @return
     */
    public static Node mergeLists(Node l1, Node l2, Node node) {
        // 如果有链表先为空，那么就将另外一个链表接入到新的链表上
        if (l1 == null) {
            node.next = l2;
            return node;
        }
        if (l2 == null) {
            node.next = l1;
            return node;
        }
        // 定义好头节点后，分别比较两个链表中的元素，哪个小哪个就先插入到新链表的后面，每次插完后，删除链表节点(移到下一个节点)
        if (l1.getData() > l2.getData()) {
            node.next = new Node(l2.getData(), null);
            l2 = l2.next;
        } else {
            node.next = new Node(l1.getData(), null);
            l1 = l1.next;
        }
        return mergeLists(l1, l2, node.next);
    }
 
 
    public static void main(String[] args) {
        Node current;
        // 定义新链表的头节点
        if (one.getData() > two.getData()) {
            current = new Node(two.getData(), null);
            two = two.next;
        } else {
            current = new Node(one.getData(), null);
            one = one.next;
        }
        mergeLists(one, two, current);
        System.out.println(current.traverse());
    }
}

打印结果:

此方法的最坏时间复杂度为o(n)，如果链表的长度差距很大的话，最后可以少比较很多次。

类似问题

        归并排序。

        上述的合并方法有点类似归并排序的思想，只不过是给的链表已经是排序好了的，归并排序的思想如下:

        1)  将数列均分成2个数列，然后分别对2个数列进行排序。

        2)  创建一个新的数列，然后使用2个指针分别指向2个数列，将相对较小的值放入到新的数列里。

        3) 将剩余的数列放入到新数列后面，然后重复上述步骤，直到排序完毕。

    public static int[] mergeSort(int[] nums, int l, int h) {
        if (l == h) {
            return new int[]{nums[l]};
 
        }
        int mid = l + (h - l) / 2;
        //左有序数组
        int[] leftArr = mergeSort(nums, l, mid);
        //右有序数组
        int[] rightArr = mergeSort(nums, mid + 1, h);
        //新有序数组
        int[] newNum = new int[leftArr.length + rightArr.length];
        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length) {
            newNum[m++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            newNum[m++] = rightArr[j++];
        }
        return newNum;
    }

扩展

        求K个升序链表的合并结果。

思路一

        暴力破解法。 采用一个List装下所有的升序链表，然后使用排序，再将排序后的链表放入到一个链表里。

    /**
     * 扩展: k 个有序链表怎么合并
     * extension:  Merge  k sorted lists and return it as one sorted list, analyze and describe its complexity.
     * use brute force method  暴力破解法
     */
    private static Node mergeManyList(List<Node> nodeList) {
        List<Integer> numLists = new ArrayList<>();
        for (Node node : nodeList) {
            while (node != null) {
                numLists.add(node.getData());
                node = node.next;
            }
        }
        // 默认采用插入排序
        Collections.sort(numLists);
        Node node = new Node(numLists.get(0));
        Node head = node;
        for (int i = 1; i < numLists.size() - 1; i++) {
            head.setNext(new Node(numLists.get(i)));
            head = head.next;
        }
        return node;
    }

 思路二

        采用纵向查找的方法，定位第一个值为最小值，将后续的最小值不断的接入到链表后面即可。

        每次比较出K个链表的头节点的最小值，下标为index, 每找到一个最小的值，需要将该节点删除掉, 方法如下:

 nodeList.set(index, nodeList.get(index).next);

         最后当nodeList列表的所有链表都为空时，暂停循环。

 
    /**
     * 纵向查找, 每次找出最小的将head的next指针执行最小的元素即可。
     * @param nodeList
     * @return
     */
    private static Node mergeListNode(List<Node> nodeList) {
        Node head = new Node(Integer.MAX_VALUE);
        Node current = head;
        while (true) {
            boolean isBreak = true;
            Node min = new Node(Integer.MAX_VALUE);
            int index = -1;
            for (int j = 0; j < nodeList.size(); j++) {
                if (nodeList.get(j) != null && nodeList.get(j).getData() < min.getData()) {
                    min = nodeList.get(j);
                    // to find the minimum index
                    index = j;
                }
                // stop the loop until nodeList become empty
                if (nodeList.get(j) != null) {
                    isBreak = false;
                }
            }
 
            if (isBreak) {
                break;
            }
            // remove the head node in time
            nodeList.set(index, nodeList.get(index).next);
            //  add node which is minimum after  the node of current.
            head.next = min;
            head = head.next;
        }
 
        return current.next;
    }

打印结果: