题解 | #合并两个排序的链表#

谁在移动？

个人理解：本题需要动动脑筋的地方在于：谁在移动?

1. 两个指针的值小的先开始移动(runner)，直至找到比另一个值大的结点(runner.next)时停止
2. 这说明一直不动的结点(stop)应该在一直移动的结点和移动停止时的结点之间
3. 改变结点链接顺序runner.next=stop；此时runner为原来的stop，stop为runner.next
   本质上是找到大值结点的后，另一条链表上的指针开始移动，移动的指针在两条链表上来回跳转 需要抽象出runner和stop，就不需要再考虑该在那条链表上移动了

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;
        ListNode runner,stop,res,temp;
        //初始值小的是runner，大的是stop
        if(list1.val>list2.val){
            runner=list2;
            stop=list1;
        }
        else{
            runner=list1;
            stop=list2;
        }
        res=runner;
        while(true){
            while(runner.next!=null&&runner.next.val<=stop.val){
                runner=runner.next;
            }
            if(runner.next==null){
                runner.next=stop;
                return res;
            }
            else{//更改链接顺序并交换runner和stop
                temp=runner.next;
                runner.next=stop;
                runner=stop;
                stop=temp;
            }
        }
    }
}