Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
解法1: 递归
https://mp.weixin.qq.com/s/7Tqc84twkk3bRmIebxwWAg
自上而下思考，递归就是将问题向下分解成若干相同子问题，直到子问题规模最小，无法继续分解，即base case，求得最小问题的解后，再依次向上归。
递归两个两个条件：1）子问题调用同一个递归函数 2）递归终止条件（递到最小子问题，返回，向上归）
/** * 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; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null) { return l2; } if(l2 == null) { return l1; } if(l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } } }
解法2:
新建一个链表，需要两个Node，一个始终指向头结点，另一随着链表的增长而移动，始终指向链表最后。
每次插入当前l1 l2中最小值。
当一个链表遍历完后，另一个未完成的链表直接链入新链表的末尾。
/** * 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; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode result = new ListNode(0); ListNode cur = result; while(l1 != null && l2 != null) { if(l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 == null) ? l2 : l1; return result.next; } }
LeetCode21.-Merge Two Sorted Lists-Easy
原文：https://www.cnblogs.com/Jessiezyr/p/12962898.html