[검지 offer-Java 버전] 17 두 개의 정렬 체인 테이블 병합

3163 단어
두 개의 정렬 체인 테이블 통합: 흔히 말하는 내용은while 순환 또는 귀속
주의: 입력 체인 테이블에 비어 있거나 두 개의 비어 있음

    public class _Q17 {

    public ListNode<Integer> Merge(ListNode<Integer> list1, ListNode<Integer> list2){

        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode result = null;

        if(list1.value < list2.value){
            result = list1;
            result.next = Merge(list1.next, list2);
        }else{
            result = list2;
            result.next = Merge(list1, list2.next);
        }

        return result;
    }

    }

테스트 코드:

    public class _Q17Test extends TestCase {

    _Q17 merge = new _Q17();

    public void test(){
        ListNode node1 = new ListNode();
        ListNode node2 = new ListNode();
        ListNode node3 = new ListNode();
        ListNode node4 = new ListNode();

        node1.value = 1;
        node2.value = 3;
        node3.value = 5;
        node4.value = 7;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;

        ListNode node5 = new ListNode();
        ListNode node6 = new ListNode();
        ListNode node7 = new ListNode();
        ListNode node8 = new ListNode();

        node5.value = 2;
        node6.value = 4;
        node7.value = 6;
        node8.value = 8;

        node5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = null;

        ListNode result = new ListNode(); 
        result.next = merge.Merge(node1, node5);
        CommonUtils.PrintList(result);
    }
    }

좋은 웹페이지 즐겨찾기