1. 基本的解题套路和方法

1.1 反转单链表

链表问题最经典的模版代码
设置三个额外的变量，遍历结束时，pre指向最后一个节点，cur和next都指向null

public ListNode reverseList(ListNode head) {
    // 设置额外两个指针
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;
    //从头反转到尾
    while(cur!=null){
        // 先记录下一个
        next = cur.next;
        // 当前的反转
        cur.next = pre;
        // 更新到下一个, 下面两行代码顺序不可调换！
        pre = cur;
        cur = next;
    }

    //指定次数的反转
    while(reverseLength-- > 0){
        nextNode = curNode.next;
        curNode.next = preNode;
        // 更新
        preNode = curNode;
        curNode = nextNode;
    }
    return pre;
}

1.2 增加dummy节点

在一些删除问题和遍历问题中，为了防止出现单独处理头节点的情况或者头节点被删除，需要换头，可以增加一个虚拟节点，让头节点指向它。

// 设置一个虚拟节点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode pre = dummyNode;
while(pre != null){
    //对pre.next的一些列操作
    pre = pre.next;
}
return dummyNode.next;

1.3 快慢指针

设置两个指针，通常一个快一个慢，一前一后，且他们保持一定的间距，一起遍历链表，结束条件是快指针决定的。

1.4 链表的长度

单链表如果需要统计它的长度可以用如下模版

ListNode cur = head;
int len = 0;
while(cur!=null){
    cur = cur.next;
    ++len;
}

2. 题目

2.1 反转

反转链表

Nr. 206
反转一个单链表。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1.迭代方法
略
2.递归方法

比较难以理解，配合动图实用更佳

还有递归方法的详细拆解

public ListNode reverseList(ListNode head) {
    //递归终止条件是当前为空，或者下一个节点为空
    if(head==null || head.next==null) {
        return head;
    }
    //这里的cur就是最后一个节点
    ListNode cur = reverseList(head.next);
    //这里请配合动画演示理解
    //如果链表是 1->2->3->4->5，那么此时的cur就是5
    //而head是4，head的下一个是5，下下一个是空
    //所以head.next.next 就是5->4
    head.next.next = head;
    //防止链表循环，需要将head.next设置为空
    head.next = null;
    //每层递归函数都返回cur，也就是最后一个节点
    return cur;
}

反转链表II

Nr. 92
题目描述:

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
保证1<=m<=n<=链表长度
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解题思路:
设置一个beforeLeft节点，记录前一个反转区域，设置一个afterRight节点，记录最后一个反转的下一个节点。
先找到leftNode节点，从这里进入，开始按照普通翻转方法开始，到结束时，preNode指向rightNode，cur指向afterRight节点。
再根据L是否等于1，决定是否处理头节点。

1.链表原始情况

2.不换头

beforeLeftNode.next = preNode;
leftNode.next = curNode;
return head;

3.换头

head = preNode;
leftNode.next = curNode;
return head;

4.整体代码

public static ListNode reverseList(ListNode head, int L, int R){
    // 1. 找到反转区域的前一个节点 beforeLeftNode
    ListNode beforeLeftNode = null;
    // 找到开始反转的右节点
    ListNode leftNode = head;
    if(L == 1){
        beforeLeftNode = null;
        leftNode = head;
    }else {
        // L >= 2
        beforeLeftNode = head;
        int temp = m;
        //注意这里的次数，若temp为2直接跳过while循环
        while(--temp>1){
            beforeLeftNode = beforeLeftNode.next;
            }
        leftNode = beforeLeftNode.next;
    }

    // 2. 先确定反转区域
    int reverseLength = R-L+1;
    // 从curNode开始是入口
    ListNode curNode = leftNode;
    ListNode nextNode = null;
    ListNode preNode = null;
    // R-L+1 次
    while(reverseLength-- > 0){
        nextNode = curNode.next;
        curNode.next = preNode;
        // 更新
        preNode = curNode;
        curNode = nextNode;
    }
    // 反转完毕，处理头节点 和 两个端节点
    // 反转结束时, 和普通反转链表一样，preNode指向反转的最后一个节点，cur和next都指向下一个节点
    if (L == 1){//考虑要换头节点
        head = preNode;
        System.out.println("换头了");
    }else {
        beforeLeftNode.next = preNode;
    }

    leftNode.next = curNode;
    return head;
}

链表k个一组反转

Nr.25
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

解题思路:

1. 每个k组反转，都要找到他们的前驱节点，但是以头节点开始的那一组没有前驱节点，因此定义一个假的节点，假节点的next指向head。
   dummy->1->2->3->4->5

2. 初始化pre和end都指向dummy。pre指每次要翻转的链表的头结点的上一个节点。end指每次要翻转的链表的尾节点

3. 当end不为null, end先遍历k次到指定位置，如果剩下的链表长度不足K，立刻退出，不用反转；
   找到本次链表的开始节点start, 它也是反转结束后的最后一个节点，也会是本次更新的pre和end;
   再记录下次要反转的部分的开头, next;
   断开本次k长度的部分,方便反转链表的子函数;
   执行局部反转, 返回反转后的头节点;
   start.next会因为反转函数变为null，通过.next把断开的链表重新链接。

public static ListNode reverseKGroup(ListNode head, int k){
    if (head == null || head.next == null){
        return head;
    }
    // 需要两个节点 pre 和 end，分别记录反转区域的前缀和最后一个反转区域
    // 建立一个虚拟节点dummy, 记录头节点的前缀
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre = dummy;
    ListNode end = dummy;
    // 建立两个节点 start 和 next, 分别记录开始反转的节点 和 下一批要反转的节点
    while(end!= null){
        // end 遍历k次到指定位置
        for(int i=0; i<k && end!=null; i++){
            end = end.next;
        }
        if (end == null){
            // 剩下的链表长度不足K，立刻退出，不用反转
            break;
        }
        // 找到本次链表的开始节点, 它也是反转结束后的最后一个节点，也会是本次更新的pre和end
        ListNode start = pre.next;
        // 记录下次要反转的部分的开头
        ListNode next = end.next;
        // 断开本次k长度的部分
        end.next = null;
        // 执行局部反转, 返回反转后的头节点
        pre.next = reverseList(start);
        // start.next会因为反转函数变为null，通过.next把断开的链表重新链接。
        start.next = next;
        pre = start;
        end = start;
    }
    return dummy.next;
}

2.2 删除

删除链表节点(力扣版)

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:
请在这里输入引用内容
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

解题思路:
设置一个虚拟节点，防止删除的节点是head，这样分情况讨论很麻烦。

public ListNode deleteNode(ListNode head, int val) {
    if(head == null){
        return null;
    }
    // 设置一个虚拟节点
    ListNode dummyNode = new ListNode(-1);
    dummyNode.next = head;
    ListNode pre = dummyNode;
    while(pre!=null){
        // 发现待删除的点
        if(pre.next.val == val){
            // pre.next -> cur, pre指向下一个节点，绕过待删除节点
            pre.next = pre.next.next;
            // 结束循环
            break;
        }
        pre = pre.next;
    }
    return dummyNode.next;
}

删除链表节点(剑指版)

待删除节点不是以val给出，而是以ListNode的形式给出的。如何做到时间复杂度O(1)。
解题思路:
类似于乾坤大挪移，把待删除节点的后一个元素赋值(val和next)给待删除节点，也就相当于删除了当前元素。
如果删除的节点是尾节点，就需要从头遍历到尾节点的前一个节点，把它删除。这个复杂度是O(n)。但最后的平均复杂度是O(1)。

class deleteNode {public static ListNode deleteNode(ListNode head, ListNode val){
        if (head == null || val == null){
            return null;
        }
        if (val.next != null){   // 待删除节点不是尾节点
            ListNode next = val.next;
            val.val = next.val;
            val.next = next.next;
        } else if (head == val){   // 待删除节点只有一个节点，此节点为头节点
            head = null;
        } else {   // 待删除节点为尾节点
            ListNode cur = head;
            while (cur.next != val){
                cur = cur.next;
            }
            cur.next = null;
        }
        return head;
    }
}

掌握了这个思想，这道题就可以秒了, 删除中间节点

删除排序链表中的重复元素 II

Nr.82
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例 1:
请在这里输入引用内容
输入: 1->2->3->3->4->4->5
输出: 1->2->5

解题思路:
链表可能会删除头节点，因此设置一个虚拟节点dummy。并设置快慢指针，其中当慢指针和快指针相等时，说明相邻节点是相等的，让快指针一直遍历到不相等的位置，把它们一并删除。

public ListNode deleteDuplicates(ListNode head) {
    // 边界条件: 空链表，只有一个节点的链表，不会发生删除
    if(head == null || head.next == null){
        return head;
    }
    // 先建立虚拟节点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode left = dummy;
    ListNode right = head;
    // 开始遍历，直到right到达最后一个节点, 这里的第一个条件是兼顾到内层的while循环
    // 因为比较的是right.next，所以它不能为null
    while(right!=null && right.next!=null){
        // 如果不相等，则向下遍历
        if(left.next.val != right.next.val){
            left = left.next;
            right = right.next;
        }else{ // 有相同节点
            // 逻辑判断的短路效应: 条件的顺序是有关系的
            // 遍历到不相等的位置，退出循环时left在相等节点的前一个，right在不相等节点
            while(right!=null && left.next.val==right.val){
                right = right.next;
            }
            // 让left指向right，跳过所有的相等节点
            left.next = right;
        }
    }
    return dummy.next;
}

删除排序链表中的重复元素

Nr. 83

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:
请在这里输入引用内容
输入: 1->1->2
输出: 1->2

解题思路:
和82相比，这道题我们可以推断出，头节点一定不会被删除，因为是升序链表，因此不用设置虚拟节点，直接用快慢指针解决。因为没有虚拟节点，不用像82那样比较快慢指针的next，而是直接比较。

public ListNode deleteDuplicates(ListNode head) {
    if(head == null){
        return null;
    }
    ListNode left = head;
    ListNode right = head.next;
    while(right!=null){
        // 不相等时，遍历到下一个，始终保持快慢间距
        if(left.val != right.val){
            left = left.next;
            right = right.next;
        }else{
            // 找到不相等的点
            while(right!=null && left.val == right.val){
                right = right.next;
            }
            // 退出循环时，right为不相等的第一个数, left为第一个相等的数
            left.next = right;
        }
    }
    return head;
}

2.3 交点/环/合并

两个链表的第一个公共节点

Nr. 剑指 Offer 52.
输入两个链表，找出它们的第一个公共节点。

解题思路:
设置两个指针，一起遍历，若有公共交点一定是两个指针同时到达，所有第一种思路是统计两个链表的长度，让长链表的指针先走，走到短链表的头，然后再一起走。
另一种就是，两个指针从头一起遍历，当到达末尾时，让两个指针分别指向对方的头节点，若有交点，一定会相遇。若没有交点，最后一起为null，退出循环。原理就是短链表的快指针走得快，让他再去长链表遍历，最后会一起同步。
原理是, 两个链表长度分别为L1+C、L2+C， C为公共部分的长度，第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时相交。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null){
        return null;
    }
    // 虐狗法
    ListNode p1 = headA;
    ListNode p2 = headB;
    while(p1 != p2){
        p1 = p1 != null ? p1.next : headB;
        p2 = p2 != null ? p2.next : headA;
    }
    return p1;
}

合并两个排序的链表

Nr. 剑指 Offer 25

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
请在这里输入引用内容
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解题思路:
类似于，归并排序的思想，双指针，谁小移动谁，合并。设置一个虚拟节点模拟排序后链表的头部的前一个节点，依次添加节点，最后返回dummy.next。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 合并到第一个元素较小的链表中
    if(l1 == null && l2 == null){
        return null;
    }
    if(l1 == null){
        return l2;
    }
    if(l2 == null){
        return l1;
    }

    // 用虚拟节点来记录，最后要返回的头节点信息
    ListNode dummyNode = new ListNode(-1);
    ListNode cur = dummyNode;

    while(l1!=null && l2!=null){
        if(l1.val <= l2.val){
            cur.next = l1;
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    cur.next = l1 == null ? l2 : l1;
    return dummyNode.next;

}

环形链表

Nr. 141
给定一个链表，判断链表中是否有环。

解题思路:
我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。但是这种方法的空间复杂度是O(n)。

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}

进阶方法，借助快慢指针，让快指针每次走两步，慢指针走一步，如果链表有环，二者一定会相遇，可以想像在环形赛道内，一个运动员跑得慢一个跑得快，最后一定会套圈相遇。定量分析就是：二者的距离／速度差。

public boolean hasCycle(ListNode head) {
    if(head == null){
        return false;
    }
    // 采用快慢指针的方法
    ListNode f = head;
    ListNode s = head;
    // 在环内追逐
    boolean res = false;
    // 如果没有环，一定是fast先出条件
    while(f!=null && f.next!=null){
        f = f.next.next;
        s = s.next;
        if(f == s){
            return true;
        }
    }
    return res;
}

环形链表 II

Nr. 142
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
解题思路:
和141类似可以用哈希表，找到第一个出现过的节点就是入环节点，但缺点就是空间复杂度高。现在介绍进阶方法。详细参考

设置两个指针，一快一慢，快的(f)每次走两步，慢的(s)每次走一步。如果链表没有环，f指针会先到达null退出循环，表示无环。

如果有环，f和s一定会在环内某个位置相遇，假设环外节点a步，环内节点b步，接下来计算他们相遇时走了多少步，f每次走两步都统计进去。f指针比s多走二倍，所以f=2s，并且它们都走过了环外节点a步，且在环内转圈后相遇，因此f=s+nb，表示f走过s的步数，且在圈内多转了n次。
f = 2s 和 f = s + nb可以得出重要结论一: s=nb，就是说慢指针在相遇时已经走了nb步。

现在想要到达入环节点，每个从头节点出发走过a+nb步后都会在入环节点，因为nb是整数圈，最后还是会在入环节点处。第二个重要结论就是：慢指针只要走过a+nb步就会在入环节点处，它已经走了nb步，就差a步，借助f指针帮助它，让f在第一次相遇后，回到头部，和s指针一起走，当相遇时，一定是在入环节点。

public ListNode detectCycle(ListNode head) {
    if(head == null){
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    // 快慢指针第一次相遇，慢指针走了 nb步
    while(true){
        // 可以遍历到null，链表没有环
        if(fast==null || fast.next==null){
            return null;
        }
        // 有环
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow){
            // 相遇时，跳出循环
            break;
        }
    }
    // 此时快指针移动到头部，再走a步，慢指针也走a步，走a+nb步，一定到入环节点
    fast = head;
    while(fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

2.4 链表长度

倒序打印链表

Nr. 剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
请在这里输入引用内容
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]

解题思路:
用模版统计出链表的长度，然后分配一个数组，再从头遍历链表，把值从尾到头的填入数组中。

public int[] reversePrint(ListNode head) {
    if(head == null){
        return new int[0];
    }

    // 第一次遍历，希望得到链表的长度
    ListNode cur = head;
    int len = 0;
    while(cur!=null){
        cur = cur.next;
        ++len;
    }
    // 新建数组
    int[] res = new int[len];
    cur = head;
    int index = len-1;
    while(cur!=null){
        res[index] = cur.val;
        cur = cur.next;
        --index;
    }
    return res;
}

链表中倒数第k个节点

Nr. 剑指 Offer 22

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
请在这里输入引用内容
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

解题思路:
一种思路是统计处链表的长度，再去遍历到len-k的节点，这样不能一次遍历完。而快慢指针可以做到一次遍历完，且不用处理一些数值关系。
思路就是，让快指针先走k步，慢指针在头节点，一起遍历，当快指针到达null时，慢指针此刻就在倒数k的位置。

public ListNode getKthFromEnd(ListNode head, int k) {
    if(head == null || k==0){
        return null;
    }
    // 设置快慢指针
    ListNode former = head;
    ListNode latter = head;

    // 快指针先走k步
    while(k-- >0){
        // k 设置的超过链表长度，不合理
        if(former == null){
            return null;
        }
        // 假设是倒数第k节点，最后一次，fomer=null
        former = former.next;
    }

    // 一起移动，直到快指针先到达尾部
    while(former!=null){
        former = former.next;
        latter = latter.next;
    }
    return latter;
}

2.5 复制链表

复制一种复杂链表

Nr. 剑指 Offer 35.
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

解题思路:
这个是链表的深度拷贝，每个节点都是新建立，关键在于如果复制random的关系。可以用哈希表记录一种映射，老节点对应新节点。
遍历新节点，同时也是遍历老节点，给新节点建立他们自己的next和random关系。方法是，找到老节点的next，再通过哈希表找到对应的新节点的，同理random也是。空间复杂度是O(n)，时间复杂度O(n)

// 完成一种深度拷贝
public Node copyRandomList(Node head) {
    // 哈希表的方法
    // 用哈希表记录，老节点 和 新节点
    HashMap<Node, Node> map = new HashMap<Node, Node>();
    Node cur = head;
    while(cur!=null){
        map.put(cur, new Node(cur.val));
        cur = cur.next;
    }
    // 接下来为新节点，设置它们的 next 和 random
    cur = head;
    while(cur!=null){
        map.get(cur).next = map.get(cur.next);
        map.get(cur).random = cur.random == null ? null : map.get(cur.random);
        cur = cur.next;
    }
    return map.get(head);
}

另一种方法可以做到空间复杂度O(1)，方法就是把新链表的节点都挂在老链表的后表，这样我们也仿照哈希表，建立起新老节点的映射关系，老得Node.next 是 新的Node。

public Node copyRandomList(Node head) {
    if(head == null){
        return null;
    }
    // 空间复杂度为O(1)的方法，用老节点后面跟着新节点，代替了hash表
    Node cur = head;
    Node next = null;
    // 每次把新产生的节点放在老节点的后面
    while(cur!=null){
        // 记录老节点的下一个
        next = cur.next;
        cur.next = new Node(cur.val);
        cur.next.next = next;
        cur = next;
    }

    // 设置新节点的 random
    // 先找到老节点的random，新节点的random就是它的next
    cur = head;
    Node curCopy = null;
    while(cur!=null){
        // 记录老节点的下一个, 这次加倍了
        next = cur.next.next;
        // 新节点
        curCopy = cur.next;
        curCopy.random = cur.random == null ? null : cur.random.next;
        cur = next;
    }

    // 把新老节点拆分开，恢复成原有的样子
    // 重新设置每个节点的next
    cur = head;
    Node res = head.next;
    while(cur!=null){
        // 记录老节点的下一个, 这次加倍了
        next = cur.next.next;
        curCopy = cur.next;
        curCopy.next = next==null ? null : next.next;
        cur.next = next;
        cur = next;
    }
    return res;
}