LeetCode_19&21链表合并与删除倒数N节点

1.题目描述

删除链表的倒数第N个节点，并且返回链表的头结点

2.思路分析

链表相较于数组的优势就是在于删除操作和插入操作的高效率即：
①找到待删除节点的前一个节点
②该节点指向待删除节点的下一个节点
没了。
思路一：
先遍历一遍节点，获得链表的长度，然后再次遍历，找到链表倒数n+1个节点
思路二：
如何实现只遍历一次链表完成操作呢？
早晚指针！
我们先让第一个指针走N-1步，第二个只能开始走，第一个指针指向末尾时，第二个指针便是指向倒数第n个指针。

3.代码实现

public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode temp=new ListNode(0);
        temp.next=head;
        ListNode l1=temp;
        ListNode l2=temp;
        for (int i = 0; i <= n; i++) {
            l1 = l1.next;
        }

        while (l1 != null) {
            l1 = l1.next;
            l2 = l2.next;
        }
        l2.next = l2.next.next;
        return temp.next;
    }

---

1.题目描述

合并两个有序的链表，返回头结点

2.思路分析

方法一：（迭代）
这里有点像归并排序的一个子步骤，先比较两个链表的首节点哪个小，哪个添加

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode root = new ListNode(-1);
        ListNode head=root;
        
        //当两个链表都为空的时候退出循环
        while (l1!=null||l2!=null){
        //获取两个链表的首元素值，如果为空，则赋值一个很大的数
            int val1=l1==null?Integer.MAX_VALUE:l1.val;
            int val2=l2==null?Integer.MAX_VALUE:l2.val;
            if(val1>val2){
                ListNode newNode=new ListNode(val2);
                head.next=newNode;
                head=head.next;
                l2=l2.next;
            }else{
                ListNode newNode=new ListNode(val1);
                head.next=newNode;
                head=head.next;
                l1=l1.next;
            }
        }
        return root.next;
    }

方法二：（递归）
递归的代码看起来就超级简洁，就是有点难理解
我们可以列出一个通项公式：

递归的通项公式
也就是说链表头部较小的一个与 剩下元素的merge操作结果 合并

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;
        }

    }