LeetCode Hot100 Day2

合并两个有序链表

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

思路：

两边依次比较大小，如果两个有其中一个读完，直接将另一个链表剩下的返回即可。其实就是更改两个链表的连接顺序，如标准图解：

代码（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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

思路：

思考最后一级有几种到达方法：到达n级的上一步一定在n-1或n-2级，而n-1对应一步，n-2对应两步，n自然为3步；设步数为因变量f，级数为自变量n，就有f(n)=f(n-1)+f(n-2)；就是把到达每一级的步数列出来就是熟悉的斐波那契数列。

因为只考虑最后一级的步数，可以动态的保存ans变量，每计算完一级将val1,val2,ans相应都向后移动一级即可。

代码（Java）：

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int ans = 0;
        int val1 = 1;
        int val2 = 2;
        for (int i = 3; i <= n; i++) {
            ans = val1+val2;
            val1 = val2;
            val2 = ans;
        }
        return ans;
    }
}