合并两个有序的单链表

　　

　　给定两个有序单链表的头节点 head1 和 head2，合并两个有序链表，合并后链表依然有序，并返回合并后的链表的头节点，例如：0->2->3->7->null   和   1->3->5->7->9->null，合并后的链表为 0->1->2->3->3->5->7->7->9->null。

 

　　【解题思路】

　　如果两个链表的长度分别为M 和 N ,那么时间复杂度可以做到 O(M+N),空间复杂度可以做到O(1)

　　1. 如果有一个为空，直接返回另一个

　　2. 比较两个头节点的值，较小的作为新的头节点

　　3. 每次比较时，cur1和cur2 分别表示两个链表的值，pre永远表示上次比较时较小的值

package com.test;import com.test.ListNode;/** * Created by Demrystv. */public class MergeTwoSortedListNode {    public ListNode merge(ListNode head1, ListNode head2){        if (head1 == null | head2 == null){            return head1 == null ? head2 : head1;        }        ListNode head = head1.val < head2.val ? head1 : head2;        ListNode cur1 = head == head1 ? head1 : head2;        ListNode cur2 = head == head1 ? head2 : head1;        ListNode pre = null;        ListNode next = null;        while (cur1 != null && cur2 != null){            if (cur1.val < cur2.val){                //这两句就是相当于指针的移动                pre = cur1;                cur1 = cur1.next;            }else {                //这一句就是先保存值                next = cur2.next;                //这两句指的是从上面的cur1切换过来，再切换回去                pre.next = cur2;                cur2.next = cur1;                //这两句就是相当于指针的移动                pre = cur2;                cur2 = next;            }        }        //针对空的情况做判断        pre.next = cur1 == null ? cur2 : cur1;        return head;    }}