剑指offer之合并两个排序的列表

合并两个排序的列表

欢迎关注作者简书
csdn传送门

题目

  输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的，并返回合并后的头结点。

思路

  假如List1中的头节点是小于List2中的，那么新的链表的头节点必将是List1的头节点，同理对List2也一样，那么在比较完头节点之后，再将List1中的下一个节点再与List2中的头节点比较，同样谁小谁进入新链表，然后再比较，直到两个链表比较完，故可用非递归或递归两种方式来做。
  若链表1的头节点小于链表2的头节点，则小值的头节点成为合并后链表的头节点。两个链表在第一次合并后，剩下的节点依然是排序的，因此合并这两个链表的步骤和前面一样，比较头节点的值，再把小值的头节点插入合并链表中。可以发现，这个合并的过程是重复的，可以定义一个递归函数完成这一系列的合并操作。
  确定解决办法后，考虑函数的鲁棒性，每当代码试图访问空指针指向的内存时程序都会崩溃，从而导致鲁棒性问题。在该问题中，传入的两个头节点都有可能为空，所以我们要对空链表进行处理。如果第一个链表为空链表，那么直接返回第二个链表即可；如果第二个链表为空链表，那么直接返回第一个链表；如果两个链表都是空链表，则返回空。

源码

/**
 * @program:
 * @description: 输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的，并返回合并后的头结点。
 * @author: zhouzhixiang
 * @create: 2018-11-09 21:40
 */
public class Test16 {

    public static class ListNode {
        int data;
        ListNode next;
    }

    /**
     * 推荐使用此方法
     * @param head1  第一个有序列表
     * @param head2  第二个有序列表
     * @return
     */
    public static ListNode merge1(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        ListNode root = new ListNode();
        ListNode move = root;
        while (head1 != null && head2 != null) {
            if(head1.data < head2.data) {
                move.next = head1;
                head1 = head1.next;
            }else {
                root = head2;
                root.next = head2;
                head2 = head2.next;
            }
            move = move.next;
        }
        // 未空链表元素处理
        if(head1.next!=null) move.next = head1;
        if(head2.next!=null) move.next = head2;
        // 返回头结点
        return root.next;
    }

    /**
     * 递归
     * 不推荐
     * 递归调用的时候会有方法入栈，需要更多的内存
     * @param head1  第一个有序列表
     * @param head2  第二个有序列表
     * @return
     */
    public static ListNode merge2(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;
        ListNode root = head1;
        if(head1.data < head2.data) {
            root.next = merge2(head1.next, head2);
        }else {
            root = head2;
            root.next = merge2(head1, head2.next);
        }
        return root;
    }
}

欢迎加入Java猿社区

欢迎加入Java猿社区.png