0406_合并两个有序链表

Algorithm：合并两个有序链表¶

题目描述¶

leecode-MergeTwoSortedLists

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

b站讲解视频

示例¶

输入: 1->2->4, 1->3->4 输出: 1->1->2->3->4->4

题目解析¶

方法1：新建一个空链表，比较val，指针就指向较小的那个

方法2：利用归并排序的思想，递归计算

java代码¶

 /**
  * Definition for singly-linked list. 
  */   
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

    /**
     * 方法1
     * @return
     */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
                tail = tail.next; // 指针向后移
            } else {
                tail.next = l2;
                l2 = l2.next;
                tail = tail.next;
            }
        }
        while (l1 != null) {
            tail.next = l1;
            l1 = l1.next;
            tail = tail.next;
        }
        while (l2 != null) {
            tail.next = l2;
            l2 = l2.next;
            tail = tail.next;
        }
        return head.next;
    }

    /**
     * 方法2
     * @return
     */
     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2; // 只是return一个链表为空后另一个链表剩下的结点
        }
        if (l2 == null) {
            return l1; // 只是return一个链表为空后另一个链表剩下的结点
        }
        if (l1.val <= l2.val) {
           l1.next = mergeTwoLists(l1.next, l2);
            return l1;  // return的头结点 
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2; // return的头结点
        }

    }

  // 或者
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2; 
        }
        if (l2 == null) {
            return l1; 
        }
        ListNode head = null;
        if (l1.val <= l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }