题目

有两个有序的链表,保证合并完之后依然有序,然后返回链表的头结点.
例子如下:
链表1:1->3->5->7->null
链表2:2->4->6->null
合并之后1->2->3->4->5->6->7->null
分析
我们来想想到底需要几个变量,想我们以前实现过的逆序单链表,我们需要用到pre来记录上一个结点,一开始默认为null,然后我们又定义了next,用来保留现场,对于这道题,我们首先想的应该是找到一个基准链表,然后不断的想这个基准链表中插值,经过分析之后,我们选定了要使用链表1作为基准链表(是针对于上面的例子来说的),我们需要找到头结点最小的作为基准链表.
现在我们的第一个问题解决了,然后我们来想一下,到底该如何完成操作那,其中肯定要需要插入操作的,由此我们要想到使用一个pre来保存插入位置之前的那个值,当然这个值,肯定是一直出现在基准链表上,也就是cur1(使用题目的例子来说).然后就是next变量,就像逆序单链表似的,我们来保留下面一个结点,这个结点肯定是cur2上的,也就是这个链表的结点一直一直的进入基准链表.
next的变量在链表的操作中一直是出现的,不止针对于这一道题.
根据上面的分析我们大概能写出大概的问题了:

while()
{
       if(cur1.value<cur2.value)
       {
                pre=cur1;
                cur1=cur1.next;
       }
       else{
               next=cur2.next;
               pre.next=cur2;
               cur2.next=cur1;
               pre=cur2;
               cur2=next;
      }
}

然后再将我们提出的第一个问题解决,整个代码如下:

public static Node mergeTwoList(Node head1,Node head2)
    {
        if(head1==null||head2==null)
        {
            return head1!=null?head1:head2==null?null:head2;
        }
    
        Node cur1=head1.value<head2.value?head1:head2;
        Node cur2=head1==cur1?head2:head1;
        Node tmp=cur1;
        Node pre=null;
        Node next=null;
        while(cur1!=null&&cur2!=null)
        {
            if(cur1.value<cur2.value)
            {
                pre=cur1;
                cur1=cur1.next;
            }else //
            {
                next=cur2.next;
                cur2.next=cur1;
                pre.next=cur2;
                pre=cur2;
                cur2=next;
            }
        }
        if(cur1==null)
        {
            pre.next=cur2;
        }
        return tmp;
    }