合并两个排序的链表

题目

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

 

思路

先判断输入的链表是否为空的指针。如果第一个链表为空，则直接返回第二个链表；如果第二个链表为空，则直接返回第一个链表。如果两个链表都是空链表，合并的结果是得到一个空链表。

两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表中的值小，即赋给合并链表指针即可。使用递归就可以轻松实现。

 

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

比较两个链表的首结点，哪个小的的结点则合并到第三个链表尾结点，并向前移动一个结点。

    步骤一结果会有一个链表先遍历结束，或者没有

    第三个链表尾结点指向剩余未遍历结束的链表

    返回第三个链表首结点

代码

自己牛客网通过的代码

public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newNode = new ListNode(-1);
        ListNode p = newNode;
            while(list1 != null && list2 != null){
                if(list1.val <= list2.val){
                   p.next  =  list1;
                    list1 = list1.next;
                }else{
                   p.next  =  list2;
                    list2 = list2.next;
                }
                 p = p.next;
            }
            if(list1 != null){
                p.next  = list1;
            }
            if(list2 != null){
                p.next  = list2;
            }
        return newNode.next;
    }

迭代

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null && list2 == null){
            return null;
        }
        if(list1 == null && list2 != null){
            return  list2;
        }
        if(list1 != null && list2 == null){
            return list1;
        }
        ListNode newHead = null;
        if (list1.val <= list2.val) {
            newHead = list1;
            newHead.next = mergeTwoLists(list1.next,list2);
        }else {
            newHead = list2;
            newHead.next = mergeTwoLists(list1,list2.next);
        }

        return newHead;
    }
}

LeetCode

 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

 

示例：

 

输入：1->2->4, 1->3->4

输出：1->1->2->3->4->4