第二期：链表经典例题（两数相加，删除链表倒数第N个节点，合并两个有序列表）

每道题后都有解析帮助你分析做题，答案在最下面，关注博主每天持续更新。
PS：每道题解题方法不唯一，欢迎讨论！

1.两数相加

题目描述
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
这两个数都不会以 0 开头。
请你将两个数相加，并以相同形式返回一个表示和的链表。
示例
输入： l1 = [1，2，3]， l2 = [4，5，6] 输出：[4，7，9]
输入：l1 = [1，2]，l2 = [9] 输出：[0，3]
解析
由于链表数字是逆序方式存储的，所以两个链表对应节点值可以相加，将它放入新的链表中。
但由于每个节点只能储存一位数字，所以两个节点相加的值放入时需要（l1.val + v2.val) % 10，创建一个变量carry = (v1.val + l2.val) / 10接受进位值。
在进行下面节点的时候，carry参与运算，放入新链表的值就变成（l1.val + l2.val + carry) % 10, carry = (l2.val + l1.val + carry) / 10。
如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个
0。
此外，如果链表遍历结束后，有carry > 0,新链表的需要在添加一个值为carry的节点。

2. 删除链表倒数第N个节点

题目描述
给你一个链表，删除链表倒数第N个节点，并返回链表头节点。
示例
输入: head = [1，2，3，4，5]，n = 3 输出: [1，2，4，5]
输入: head = [1，2，3]，n = 3 输出: [2，3]
输入: head = [ 1 ]，n = 1 输出: []
解析
不知道你们看到这道题第一想法是什么，我的第一想法就是前后双指针，使用两个指针fast和slow一前一后遍历。
由于要删除倒数第n个节点，所以fast先遍历，当fast比slow快n个节点时，两个指针同时遍历链表。
当fast指针的下一个节点为null时，slow指针的下个节点刚好是要删除的节点，这个时候只需要将slow.next指向slow.next.next即可。
注意一些特殊情况，当fast指针先走时，fast为null时，说明删除节点不存在，返回null；当fast先走完时，fast为null，说明删除节点为头节点，直接返回头节点的下一个节点。

3. 合并两个有序列表

题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入：l1 = [1,3,5], l2 = [1,4,5] 输出：[1,1,3,4,5,5]
输入：l1 = [], l2 = [] 输出：[]
输入：l1 = [], l2 = [1] 输出：[1]
解析
这题可以使用递归，也可以迭代，就是遍历两个链表，一个一个比较。
这里我介绍一下递归：
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点，如l1.val < l2.val; l1.next = mergeTwoLists(l1.next,l2);如果两个链表有一个为空，递归结束。

答案

1. 两数相加

> public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        int count = 0;
        while(l1 != null && l2 != null){
            cur.next = new ListNode(((l1.val + l2.val + count) % 10));
            count = (l1.val + l2.val + count) / 10;
            cur = cur.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null){
            cur.next = new ListNode((l1.val + count) % 10);
            count = (l1.val + count) / 10;
            cur = cur.next;
            l1 = l1.next;
        }
        while(l2 != null){
            cur.next = new ListNode((l2.val + count) % 10);
            count = (l2.val + count) / 10;
            cur = cur.next;
            l2 = l2.next;
        }
        if(count > 0){
            cur.next = new ListNode(count);
        }
        return head.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2. 删除链表倒数第N个节点

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;
        for(int i = 0;i < n; i++){
            if(fast == null){
                return null;
            }
            fast = fast.next;
        }
        if(fast == null){
            return head.next;
        }
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.合并两个有序列表

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null){
            return list2;
        }else if(list2 == null){
            return list1;
        }else{
            if(list1.val < list2.val){
                list1.next = mergeTwoLists(list1.next,list2);
                return list1;
            }else{
                list2.next = mergeTwoLists(list1,list2.next);
                return list2;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15