JZ25 合并两个排序的链表

JZ25 合并两个排序的链表

合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com)

// //递归
// public class Solution {
//     public ListNode Merge(ListNode head1,ListNode head2) {
//         if(head1==null){
//             return head2;
//         }
//         if(head2==null){
//             return head1;
//         }
//         ListNode newHead=null;
//         if(head1.val<head2.val){
//             newHead=head1;
//             head1=head1.next;
//         }else{
//             newHead=head2;
//             head2=head2.next;
//         }
//         newHead.next=Merge(head1,head2);
//         return newHead;
//     }
// }


//二路归并
public class Solution {
    public ListNode Merge(ListNode head1,ListNode head2) {
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        ListNode newHead=new ListNode(-1);
        ListNode cur=newHead;
        while(head1!=null&&head2!=null){
            if(head1.val<head2.val){
                cur.next=head1;
                head1=head1.next;
                cur=cur.next;
            }else{
                cur.next=head2;
                head2=head2.next;
                cur=cur.next;
            }
        }
        if(head1!=null){
            cur.next=head1;
        }
        if(head2!=null){
            cur.next=head2;
        }
        return newHead.next;
    }
}