算法_链表_合并两个有序链表

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 * 提示：
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 */
public class 合并两个有序链表 {
    /**
     * 方法一：计数法：遍历两个list到数组中，val为下标，出现次数为数字中值，最后遍历数组
     * 问题：当输入书负数的时候有问题ArrayIndexOutOfBoundsException
     */
    public static Node.IntNode mergeTwoLists(Node.IntNode list1, Node.IntNode list2) {
        //1、创建数组
        int[] tempInts = new int[50];

        //2、将node中的值遍历放到数组中
        Node.IntNode curr1 = list1;
        Node.IntNode curr2 = list2;
        while (curr1 != null) {
            int aInt = tempInts[curr1.val];
            tempInts[curr1.val] = aInt + 1;
            curr1 = curr1.next;
        }
        while (curr2 != null) {
            int bInt = tempInts[curr2.val];//ArrayIndexOutOfBoundsException
            tempInts[curr2.val] = bInt + 1;
            curr2 = curr2.next;
        }

        //3、循环遍历数组，重新生成数组值
        Node.IntNode resNode = new Node.IntNode(-1);
        for (int i = 0; i < tempInts.length; i++) {
            int indexCount = tempInts[i];
            if (indexCount > 0) {
                for (int j = 0; j < indexCount; j++) {
                    Node.IntNode intNode = new Node.IntNode(i);
                    addNode(resNode, intNode);
                }
            }
        }

        //4、返回节点
        return resNode.next;
    }

    static void addNode(Node.IntNode root, Node.IntNode add) {

        if (root == null) {
            root = add;
            return;
        }

        Node.IntNode currRoot = root;
        while (currRoot.next != null) {
            currRoot = currRoot.next;
        }
        currRoot.next = add;
    }


    /**
     * 方法二：遍历法，先将公共部分遍历完，在拼接剩余部分
     */
    public static Node.IntNode mergeTwoLists2(Node.IntNode list1, Node.IntNode list2) {

        Node.IntNode resNode = new Node.IntNode(-1);

        Node.IntNode curr1 = list1;
        Node.IntNode curr2 = list2;

        //1、遍历公共部分
        while (curr1 != null && curr2 != null) {

            int v1 = curr1.val;
            int v2 = curr2.val;

            if (v1 < v2) {
                addNode(resNode, new Node.IntNode(v1));
                curr1 = curr1.next;
            } else {
                addNode(resNode, new Node.IntNode(v2));
                curr2 = curr2.next;
            }
        }

        //2、拼接剩余部分
        if (curr1 != null) {
            addNode(resNode, curr1);
        }

        if (curr2 != null) {
            addNode(resNode, curr2);
        }

        return resNode.next;
    }

    /**
     * 方法三：递归思想
     */
    public static Node.IntNode mergeTwoLists3(Node.IntNode l1, Node.IntNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        Node.IntNode res = mergeTwoLists3(Node.getIntNode123456789(), Node.getIntNode135());

        Node.IntNode curr = res;
        while (curr != null) {
            System.out.println("遍历 n = " + curr.val);
            curr = curr.next;
        }
    }
}