算法入门第十天

21. 合并两个有序链表

递归解法

/**
 * Question21

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



 示例 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 均按 非递减顺序 排列


 *
 * @author zeroheart
 * @since 2022/4/4
 */
public class Question21 {
    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;
        }
    }


}

206. 反转链表

/**
 * Question206
 206. 反转链表
 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。


 示例 1：


 输入：head = [1,2,3,4,5]
 输出：[5,4,3,2,1]
 示例 2：


 输入：head = [1,2]
 输出：[2,1]
 示例 3：

 输入：head = []
 输出：[]


 提示：

 链表中节点的数目范围是 [0, 5000]
 -5000 <= Node.val <= 5000

 *
 * @author zeroheart
 * @since 2022/4/4
 */
public class Question206 {
    public ListNode reverseList(ListNode head) {
        if(head==null)return head;

        // 这题放在递归下面，不过递归方法不容易理解，改成类似双指针的做法
        ListNode pre = null;
        while (head!=null){
            ListNode tmp = head.next; // 保存下一个节点
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }

}