剑指Offer：合并两个排序的链表【25】

题目描述

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

题目分析

　　双指针问题的经典案例，合并有序链表。

　　上下两个指针，谁小谁先走，先走的是较小的蓝1，结果集新增蓝1.

　　上下两个指针，谁小谁先走，先走的是较小的紫2，结果集新增紫2.

　　按照这个逻辑接着往后走即可！这个逻辑还是相对比较清晰的。

Java题解

 public ListNode Merge(ListNode list1,ListNode list2) {

        ListNode head1 = list1;

        ListNode head2 = list2;

        ListNode newHead = new ListNode(-1);

        ListNode ptr = newHead;

        while (head1!=null&&head2!=null){

            if(head1.val<=head2.val){

                ptr.next = head1;

                head1 = head1.next;

            }else{

                ptr.next = head2;

                head2 = head2.next;

            }

            ptr = ptr.next;

        }

        if(head1==null)

            ptr.next = head2;

        else

            ptr.next = head1;

        return newHead.next;

    }