JZ16_合并两个排序的链表.md

JZ16_合并两个排序的链表

思想就是对两个链表进行重定向，不改变原有的节点，但是改变每个节点的next值。

由于是两个单调递增的序列，这里用一个list3表示有序序列的头节点，rear表示有序序列的尾节点，每次选择list1，list2的较小的头节点，由rear去指向，rear更新为当前有序序列末尾，对应的list1或list2的头节点向后移动一位，重复操作，直到list1，list2中出现某个序列为空，则将另一个序列拼接到rear的后边

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //先处理某一个链表为空，或者两个链表都为空的情况
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        //list3作为返回链表的第一个节点
        ListNode list3 = null;
        //将两个非空链表的较小一方指向list3
        if (list1.val < list2.val) {
            list3 = list1;
            list1 = list1.next;
        } else {
            list3 = list2;
            list2 = list2.next;
        }
        //rear为结果链表的尾指针
        ListNode rear = list3;
        //只要两个链表都不空就继续用rear指向两个链表的头节点中小的一方
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                rear.next = list1;
                rear = rear.next;
                list1 = list1.next;
            }
            else {
                rear.next = list2;
                rear = rear.next;
                list2 = list2.next;
            }
        }
        //如果还有某个链表不空，则直接拼接上去
        if (list1 != null) rear.next = list1;
        if (list2 != null) rear.next = list2;
        return list3;
    }
}