25:2つのソートされたチェーンテーブルを結合する

タイトル25:2つのソートされたチェーンテーブルをマージ
2つの増分ソートされたチェーンテーブルを入力し、2つのチェーンテーブルを結合し、新しいチェーンテーブルのノードを増分ソートします.
例を挙げて説明する
チェーンテーブル1:10 -> 30 -> 50 -> 70;チェーンテーブル2:20 -> 40 -> 60 -> 80合併後のチェーンテーブルは:10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80構想
いくつかの点

連結後のチェーンテーブルを選択するヘッド

は、古いチェーンテーブルから切断する(.nextで後に移動する)に相当し、新しいチェーンテーブルに接続する(.nextに値を付与する)

.
一.再帰
結合チェーンテーブルの次のノードとして、2つのチェーンテーブルヘッダノードの小さな値が毎回使用されます.マージのたびに操作が同じなので、再帰を使用します.
マスターコード

    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