【剑指Offer】16、合并两个排序的链表

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路：

首先需要判断几个特殊情况，即判断输入的两个指针是否为空。如果第一个链表为空，则直接返回第二个链表；如果第二个链表为空，则直接返回第一个链表。如果两个链表都是空链表，合并的结果是得到一个空链表。

两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表中的值小，即赋给合并链表指针，剩余的结点仍然是排序的，所以合并的步骤和之前是一样的，所以这是典型的递归过程，用递归可以轻松实现。

举例：

![](https://img2018.cnblogs.com/blog/1608161/201904/1608161-20190427150721322-366814884.png)

编程实现（Java）：

	//方法一：递归实现

	public ListNode Merge(ListNode list1,ListNode list2) {

   		if(list1==null)

            return list2;

        if(list2==null)

            return list1;

        ListNode head=null;    //头节点

        if(list1.val<=list2.val){

            head=list1;

            head.next=Merge(list1.next,list2);

        }else{

            head=list2;

            head.next=Merge(list1,list2.next);

        }

        return head;

	}

	//方法二：非递归实现

	public ListNode Merge(ListNode list1,ListNode list2) {

    	if(list1==null)

            return list2;

        if(list2==null)

            return list1;

        ListNode head=new ListNode(-1);//头节点

        ListNode thehead=head;

        while(list1!=null && list2!=null){

            if(list1.val<=list2.val){

                thehead.next=list1;

                list1=list1.next;

            }else{

                thehead.next=list2;

                list2=list2.next;

            }

            thehead=thehead.next;

        }

        if(list1!=null)  //归并完需要检查哪个链表还有剩余

            thehead.next=list1;

        if(list2!=null)

            thehead.next=list2;

        return head.next;

    }

巴特西

【剑指Offer】16、合并两个排序的链表

最新文章

热门文章