首页 > 代码库 > 《剑指Offer》题目:合并两个排序的链表

《剑指Offer》题目:合并两个排序的链表

题目描述:输入两个单调递增的链表list1,list2,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

题目分析:

1.对于链表题目,首先考虑边界情况,即链表为空的情况,提升代码的鲁棒性。

2.合并完一个结点后,剩余的链表仍然是有序的,再合并下一个结点时的过程是一样的,这是一种递归的思想,因此采用递归来合并。

 

Java代码:

public class MergeSortedList {

    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode preNodeList2 = null;

        if(list1.val < list2.val){
            preNodeList2 = list1;
            preNodeList2.next = Merge(list1.next, list2);
        }
        else{
            preNodeList2 = list2;
            preNodeList2.next =  Merge(list1, list2.next);
        }

        return preNodeList2;
    }
    public static void main(String[] args){

    }
}

 

《剑指Offer》题目:合并两个排序的链表