面试题 ： 合并两个有序链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了面试题 ： 合并两个有序链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2355字，纯文字阅读大概需要4分钟。

内容图文

问题： 合并两个有序链表

链表L1: 1->2->4->9

链表L2: 3->5>6->10->13

合并后：1->2->3->4->5->6->9->10->13

1. 准备数据结构 及测试数据

Node节点

public class Node {
    public Integer value;
    public Node next;
    // 构造
    public Node(){}
    public Node(Integer value) {
        this.value = value;
    }
    public Node(Integer value,Node next) {
        this.value = value;
        this.next = next;
    }

    // 打印链表
    public void print() {
       Node n = this;
       System.out.println("------------------------------------------------");
       while (n != null) {
           System.out.print(n.value);
           n = n.next;
           if (n != null) {
               System.out.print("-->");
           } else {
               System.out.println();
           }
       }
       System.out.println("------------------------------------------------");
    }
}

准备测试数据

public class TestNode {
    public static void main(String[] args) {
        Node L1= getL1();
        Node L2= getL2();
        // 1-->2-->4-->9
        L1.print();
        // 3-->5-->6-->10-->13
        L2.print();
    }

    // 获取测试数据L1
    public static Node getL1() {
        Node head = new Node(1,new Node(2,new Node(4,new Node(9))));
        return head;
    }
    // 获取测试数据L2
    public static Node getL2() {
        Node head = new Node(3,new Node(5,new Node(6,new Node(10,new Node(13)))));
        return head;
    }
}

2.解决方案01

定义一个伪头节点Head 然后遍历L1 L2 比较Node值 小的就追加到Head后边

private static Node mergeNodes(Node l1, Node l2) {
        if (l1 == null ){
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        // 链表头
        Node head ;
        // 新链表添加的当前位置
        Node next ;
        // 先选出一个2个链表开头的最小值
        head = next = l1.value > l2.value ? l2:l1;
        // 头指针向后移动
        l1 = head == l1 ? l1.next : l1;
        l2 = head == l2 ? l2.next : l2;

        // 遍遍历2个链表
        while (l1 !=null && l2 != null) {
            // 遍历链表的最大值
            Node maxNode = null;
            // 链表1值大
            if(l1.value <= l2.value) {
                maxNode = l1;
                l1 = l1.next;
            } else {
                // 链表2值大
                maxNode = l2;
                l2 = l2.next;
            }
            // 添加到新链表 next向后移
            next.next = maxNode;
            next = next.next;
        }

        // 判断哪个链表还没有遍历完 直接加到新链表末尾
        next.next = l1 == null ? l2 :l1;
        // 返回head
        return head;
    }

3.解决方案02

定义一个伪头节点Head 然后遍历L1 L2 比较Node值 小的就追加到Head后边

使用递归 不用while循环

private static Node mergeNodesRec(Node l1, Node l2) {
        // 如果l1 链表已经遍历完了
        if (l1 == null) {
            return l2;
        }
        // 如果l2 链表已经遍历完了
        if (l2 == null) {
            return l1;
        }

        Node head ;

        if(l1.value <= l2.value) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        // 递归调用 设置next
        head.next = mergeNodesRec(l1,l2);
        return head;
    }

自己写一写、用笔画一画 可能会豁然开朗 肯定还有其他写法 欢迎留言

也可公众号留言（响应快）：

内容总结

以上是互联网集市为您收集整理的面试题 ： 合并两个有序链表全部内容，希望文章能够帮你解决面试题 ： 合并两个有序链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---