剑指offer - 合并两个有序的链表(Java实现)

题目链接：https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&&tqId=11169&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：将大的链表 list1 合并到小的链表 list2 中，首先我们设置两个指针分别指向 list1 和 list2 中的第一个元素，然后我们在 list2 中找到最后一个比 list1 指针指向的数值小的位置，然后将 list1 指向的节点插入到 list2 中，直到 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) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode ans;
        if(list2.val > list1.val) {
            ans = list1;
            list1 = list2;
            list2 = ans;
        }
        ans = list2;
        while(list2.next != null && list1 != null) {
            if(list2.next.val < list1.val) { //找到最后一个比list1小的数
                list2 = list2.next;
            } else { //将list2中的节点插入到list1中
                ListNode node = list1;
                list1 = list1.next;
                node.next = list2.next;
                list2.next = node;
                list2 = list2.next;
            }
        }
        if(list2.next == null) { //如果list2中找不到最后一个比list1小的数，那么将list1整个插入list2中
            list2.next = list1;
        }
        return ans;
    }
}

  思路二：设置头结点，建立新的链表 newList，我们一次遍历两个链表，如果list1.val < list2.val，那么将 list1 插入到新的链表中，list1 指针后移，否则新链表中插入 list2，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) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode ans = new ListNode(-1), node = ans;
        while(list1 != null && list2 != null) {
            ListNode node1 = list2.val <= list1.val ? list2 : list1;
            node.next = node1; 
            if(list2.val <= list1.val) {
                list2 = list2.next;
            } else {
                list1 = list1.next;
            }
            node = node.next;
        }
        node.next = list1 != null ? list1 : list2;
        return ans.next;
    }
}

  思路三：递归，我们可以这样思考，如果某一个链表为空，我们必定返回另外一个链表。否则，当list1.val <= list2.val时，就相当于list1作为头结点，然后list1.next和list2继续进行有序链表的合并，当list2.val <= list1.val时，相当于list2.val作为头结点，然后list2.next和list1继续进行有序链表的合并，那么按照这样的思路我们就可以写出相应的递归代码。

/*
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;
        if(list1.val <= list2.val) {
            list1.next = Merge(list1.next, list2); //list1.next和list2合并
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);//list2.next和list1合并
            return list2;
        }
    }
}