『剣指Offer』第2版の合併2つのソートのチェーンテーブル(12)

目次

題

構想

ステップ

コード

テーマ:2つのインクリメンタルソートのチェーンテーブルを入力し、この2つのチェーンテーブルを結合し、新しいチェーンテーブルのノードをインクリメンタルソートします.たとえば、チェーンテーブル1:1、3、5、7、チェーンテーブル2:2、4、6、8を入力すると、統合後の昇順チェーンテーブルがチェーンテーブル3:1、2、3、4、5、6、7、8に示されます.チェーンテーブルノードは次のように定義されます.

struct ListNode
{
	int value;
	ListNode next;
}

構想:まず2つのチェーンテーブルを統合する過程を分析する.2つのチェーンテーブルを結合するヘッダノードを解析して開始した.チェーンテーブル1のヘッダノードの値はチェーンテーブル2のヘッダノードの値よりも小さいため、チェーンテーブル1のヘッダノードはマージ後のチェーンテーブルのヘッダノードとなる.
2つのチェーンテーブルの残りのノードをマージし続けます.2つのチェーンテーブルの残りのノードは依然としてソートされているため、2つのチェーンテーブルをマージする手順は前の手順と同じです.2つのヘッダノードの値を比較します.このとき、チェーンテーブル2のヘッダノードの値は、チェーンテーブル1のヘッダノードの値よりも小さいので、チェーンテーブル2のヘッダノードの値は、残りのノードを結合して得られるチェーンテーブルのノードとなる.このノードと前にチェーンテーブルをマージしたときに得られたチェーンテーブルの末尾ノードをリンクします.
2つのチェーンテーブルの値の小さいヘッダノードを取得し、マージされたチェーンテーブルにリンクした後も、2つのチェーンテーブルの残りのノードはソートされているため、マージのステップは前のステップと同じです.これが典型的な再帰プロセスであり、このマージプロセスを完了するために再帰関数を定義することができます.
手順:略
コード:

package test;

public class ListNodeMerge {

	public static void main(String[] args) {
		ListNode ln1 = new ListNode();
		ListNode ln2 = new ListNode();
		ListNode ln3 = new ListNode();
		ListNode ln4 = new ListNode();
		ln1.value = 1;
		ln1.next = ln2;
		ln2.value = 3;
		ln2.next = ln3;
		ln3.value = 5;
		ln3.next = ln4;
		ln4.value = 7;
		
		ListNode ln5 = new ListNode();
		ListNode ln6 = new ListNode();
		ListNode ln7 = new ListNode();
		ListNode ln8 = new ListNode();
		ln5.value = 2;
		ln5.next = ln6;
		ln6.value = 4;
		ln6.next = ln7;
		ln7.value = 6;
		ln7.next = ln8;
		ln8.value = 8;
		
		ListNode listNode = merge(ln1, ln5);
		while(listNode != null) {
			System.out.println(listNode.value);
			listNode = listNode.next;
		}
	}
	
	public static ListNode merge(ListNode pHead1, ListNode pHead2) {
		if (pHead1 == null)
			return pHead2;
		else if (pHead2 == null)
			return pHead1;
		
		ListNode pMergedHead = null;
	
		if(pHead1.value < pHead2.value) {
			pMergedHead = pHead1;
			pMergedHead.next = merge(pHead1.next, pHead2);
		} else {
			pMergedHead = pHead2;
			pMergedHead.next = merge(pHead1, pHead2.next);
		}
		
		return pMergedHead;
	}
	
	static class ListNode {
		int value;
		ListNode next;
	}
}