题目25：合并两个排序的链表

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

举例说明

链表1：10 -> 30 -> 50 -> 70；链表2：20 -> 40 -> 60 -> 80
合并后的链表为：10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80

思路

几个点

• 选择好 合并后链表的头
• 每次相当于从一个老链表断开(用.next后移)，接在新链表上（为.next赋值）

一. 递归

每次以两个链表头节点中的小值作为合并链表的下一个节点。每次合并的操作都是相同的，故使用递归。

主体代码

    public static ListNode merge1(ListNode head1, ListNode head2) {//递归
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }   

        ListNode tmp = head1;//两个链表中头部较小的结点 是 新链表的头
        if (tmp.value < head2.value) {
            tmp.next = merge1(head1.next, head2);
        } else {
            tmp = head2;
            tmp.next = merge1(head1, head2.next);
        }
        return tmp;
    }

二. 迭代

主体代码

    public static ListNode merge2(ListNode head1, ListNode head2) {//迭代
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }   
        ListNode root = new ListNode();//逻辑头结点
        ListNode cur = root;// 待处理节点，每次都是正在合并后链表的尾，迭代向后

        while (head1 != null && head2 != null) {// 当两个链表都不为空就进行合并操作
            if (head1.value < head2.value) {
                cur.next = head1;//老链表节点 加入新链表（接上链子）
                head1 = head1.next;//老链表中 待处理节点后移（在老链表移除处理过的 节点）
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;//新链表中 待处理指针后移，方便下次添加
        }
        // 下面的两个if有且只一个if会内的内容会执行
        if (head1 != null) {// 如果第一个链表的元素未处理完将其
            cur.next = head1;//接到合并链表的最后一个结点之后
        }
        if (head2 != null) {
            cur.next = head2;
        }
        return root.next;//root是逻辑头结点 ；root.next是合并后的链表头
    }

总的代码含测试

public class _25 {
    private static class ListNode {
        int value;
        ListNode next;

        public ListNode() {
        }
        public ListNode(int value) {
            this.value = value;
        }
    }
    
    public static ListNode merge1(ListNode head1, ListNode head2) {//递归
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }   

        ListNode tmp = head1;//两个链表中头部较小的结点 是 新链表的头
        if (tmp.value < head2.value) {
            tmp.next = merge1(head1.next, head2);
        } else {
            tmp = head2;
            tmp.next = merge1(head1, head2.next);
        }
        return tmp;
    }

    public static ListNode merge2(ListNode head1, ListNode head2) {//迭代
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }   
        ListNode root = new ListNode();//逻辑头结点
        ListNode cur = root;// 待处理节点，每次都是正在合并后链表的尾，迭代向后

        while (head1 != null && head2 != null) {// 当两个链表都不为空就进行合并操作
            if (head1.value < head2.value) {
                cur.next = head1;//老链表节点 加入新链表（接上链子）
                head1 = head1.next;//老链表中 待处理节点后移（在老链表移除处理过的 节点）
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;//新链表中 待处理指针后移，方便下次添加
        }
        // 下面的两个if有且只一个if会内的内容会执行
        if (head1 != null) {// 如果第一个链表的元素未处理完将其
            cur.next = head1;//接到合并链表的最后一个结点之后
        }
        if (head2 != null) {
            cur.next = head2;
        }
        return root.next;//root是逻辑头结点 ；root.next是合并后的链表头
    }
    //for test
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.value + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }
    public static void main(String[] args) {
        // 10 -> 30 -> 50 -> 70
        ListNode head1 = new ListNode(10);
        ListNode n2 = new ListNode(30);
        ListNode n3 = new ListNode(50);
        ListNode n4 = new ListNode(70);
        head1.next = n2;
        n2.next = n3;
        n3.next = n4;
        // 20 -> 40 -> 60 -> 80
        ListNode head2 = new ListNode(20);
        ListNode n5 = new ListNode(40);
        ListNode n6 = new ListNode(60);
        ListNode n7 = new ListNode(80);
        head2.next = n5;
        n5.next = n6;
        n6.next = n7;

        System.out.print("原始链表1：");
        printList(head1);
        System.out.print("原始链表2：");
        printList(head2);
        System.out.print("合并后的链表：");
        //head = merge1(head, head2);
        head1 = merge2(head1, head2);
        printList(head1);
    }
}

输出：

原始链表1：10->30->50->70->null
原始链表2：20->40->60->80->null
合并后的链表：10->20->30->40->50->60->70->80->null