hot 100刷题记录

嵌套操作->递归调用
1.开头位置： 结束条件
一者为空，就不用比较了，指向非空者即可
没有嵌套，只有一步时执行的是

if(l1 
2.核心操作：l2用递归方法代替
 3.返回值：没有嵌套，只有一步的时候返回的是什么（l1即表头）。
 
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
迭代 
1.核心操作 形式
 
while(迭代未完成){
l = l+x 
l= l.next
}
 
2 开头要分配量保存返回值（不参与迭代的表头）
 3 结尾要对未结束迭代的一方特别处理
 4 要明确每个变量的含义，才能知道是否迭代
 l1：链表1的未合并头
 l2: 链表2的未合并头
 prev：新链表的尾端
 三者都需要更新
 prehead：需要返回的链表头，不能更新
 
class Solution {
    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;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}
 
5.25 206. 反转链表 
反转：x.next.next = x 且 需要避免回路
 递归：重复单元操作
 
public ListNode reverseList(ListNode head) {
    // 1. 递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    // 3.反转的核心操作
    head.next.next = head;
    //4.避免回路
    head.next = null;
    //2.两者返回值的物理含义必然相同
    return p;
}
 
迭代：递进操作
 
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}