【剑指offer-Java版】17合并两个排序链表

àì夳堔傛蜴生んèń 2022-08-21 08:58 16阅读 0赞

合并两个排序链表：老生常谈的内容了  
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);
        }
        }