剑指Offer第十六题：合并两个排序的链表

题目描述

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

思路：使用归并排序

初始化：

创建一个dummyNode，来作为头结点的前一个结点

创建一个currNode = dummyNode，来遍历链表

为了防止破坏原链表，用两个临时指针p1和p2指向list1和list2
遍历链表，将两个链表中当前头结点较小的结点归并到链表中
           

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        ListNode p1 = list1;
        ListNode p2 = list2;
        while(p1 != null && p2 != null){
            if(p1.val < p2.val){
                curr.next = p1;
                p1 = p1.next;
                curr = curr.next;
            }
            else{
                curr.next = p2;
                p2 = p2.next;
                curr = curr.next;
            }
        }
        if(p1 != null){
            curr.next = p1;
        }
        if(p2 != null){
            curr.next = p2;
        }
        return dummy.next;
    }
}