剑指Offer——合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
时间限制：1秒 空间限制：32768K
本题知识点：链表

代码实现

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode result = null;
        ListNode current = null;
        while(list1!=null && list2!=null){
            if(list1.val <= list2.val){
                if(result == null){
                    result = list1;
                    current = result;
                }else{
                    current.next = list1;
                    current = list1;
                }
                list1 = list1.next;
            }else{
                if(result == null){
                    result = list2;
                    current = result;
                }else{
                    current.next = list2;
                    current = list2;
                }
                list2 = list2.next;
            }
        }
        if(list1 == null){
            current.next = list2;
        }else{
            current.next = list1;
        }
        return result;
    }
}

解题思路

这道题还是考察的我们对链表知识的掌握，还没掌握的同学请看我前面几道题，或者去数据结构和算法系列的链表的文章。
首先，我们进行是否为空的判断，如果为空我们就直接返回另一个链表即可。
然后我们定义合并后的链表的头结点 result 和当前结点 current。当我们进行合并选取下一个结点的时候分为两种情况。第一种是链表1当前结点和链表2当前结点都不为空，然后我们选择相对较小的那个加入合并后的链表，然后把被选择的链表当前结点更新为下一个结点，然后依次循环判断；第二种情况是其中一个链表当前结点为空了，那么我们直接把另外一个链表剩余的结点合并到结果链表即可。
代码中 result 空判断，是因为 result 和 current 结点还都为空，所以直接把选择的结点赋值给 result 和 current，如果不为空，那么就把 current 的指针指向被选择结点。