给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

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

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

思路：就是遍历链表，找到所有值为val的节点，并删除即可。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 删除链表中所有值为节点
        // 首先判断链表是否为空
        if (head == null ) {
            // 链表为空，肯定head为空
            return head;
        }
        ListNode cur = head;
        while (cur.next != null) {
            // 找到值为val的前一个节点
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            }else {
                // 没找到就继续往后找
                cur = cur.next;
            }
        }
        // 判断头节点是否为val
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }
}

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

思路：遍历原链表，将其中的所有节点全部头插到原链表中。

class Solution {
    public ListNode reverseList(ListNode head) {
        // 当链表为空，或者只有一个节点时，就直接返回原链表
        if (head == null || head.next == null) {
            return head;
        }
        // 开始头插
        ListNode cur = head.next;
        // 这个要变为null，否则就会成环。
        // 因为这个节点是最后一个节点，而最后一个节点的next值不为null，就会造成错误
        head.next = null; 
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head; 
            head = cur;
            cur = curNext;
        }
        return head;
    }
}

876. 链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。
示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
提示：

链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

思路一：通过遍历链表得出链表的长度，然后让cur从头节点开始走长度的一半的步数，那么这个节点的位置就是中间节点。

思路二：通过快慢指针的方式来解题。快指针fast，一次走两步，慢指针slow，一次走一步。当快指针走到链表的尾节点处时，慢指针就是在当前链表的中间节点。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 只要两者有一种情况不满足，就说明走到了尾节点，可以停止遍历了。
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

面试题 02.02. 返回倒数第k个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 k 保证是有效的。

思路一：遍历得出链表的长度，然后用长度减去k，得出的结果就是cur要走的步数。

思路二：通过快慢指针的方式来解题。快指针先走k-1步，然后快指针和慢指针一起走，直至快指针到达尾节点，这时慢指针的位置就是倒数第k个节点的位置。

class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        while ((k-1) > 0) {
            fast = fast.next;
            k--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

快慢指针的原理分析

通过这两题，我们来分析快慢指针的原理。

链表的中间节点 —— 假设有两个人在同一时间赛跑，fast是slow的速度的二倍，当fast到达终点时，这个slow就会在这个总路程的一半处。因此就可以得出中间节点的位置。

返回倒数第k个节点 —— fast先走k-1步，那么fast与slow就相差k-1步，当两者一起走，并且fast走到了终点时，这时fast与slow还是相差k-1步，那么这个slow就是倒数第k个节点（因为fast的位置是倒数第一个节点）。

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

思路：创建一个新的带头链表。通过遍历两个链表，比较两者的大小，将小的val值对应的节点尾插到这个带头链表中，直至有一方节点结束，再把另一方的节点直接尾插到新链表即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 当list1为空或者list1与list2都为空时，直接返回list2
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 创建一个新的头节点
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val > cur2.val) {
                // 尾插cur2
                cur.next = cur2;
                cur2 = cur2.next;
            }else {
                // 尾插cur1
                cur.next = cur1;
                cur1 = cur1.next;
            }
            // 因为这一行代码无论走哪里，都会进行，因此放到外边来
            cur = cur.next;
        }
        // 还有一方还剩节点
        if (cur1 != null) {
            // 尾插cur1就行了，因为原来就是链表，因此不用循环
            cur.next = cur1;
        }
        if (cur2 != null) {
            // 尾插cur2就行了，因为原来就是链表，因此不用循环
            cur.next = cur2;
        }
        return head.next;
    }
}

牛客网——链表的回文

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：
1->2->2->1
返回：true

思路：虽然描述很简洁，但是难度却是比较大的一题。按照我们以往写回文的思路，就是定义一个left 和 right 指针指向两头，遍历比较。遇到不相等的就直接返回false，遍历完就返回true。但很可惜这题是单链表不能够反向遍历。既然不能直接反向遍历，那么我们就把这个后面的链表反转一下，变成可以反向遍历的情况。那问题又来了：从哪里开始反转呢？我们想一下，普通回文遍历的结束条件是left < right ，也就是两者相遇或者说是到了中间位置就可以停止了。那么我们这里的反转也就可以从中间位置开始。反转完，之后就可比较了。因此，最终要做的事情就是：

1. 找到链表的中间节点；

2. 从中间位置开始反转；

3. 从两头开始遍历比较。

下面是反转的具体分析过程：

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // 当链表为空或者只有一个节点时，必回文
        if (A == null || A.next == null) {
            return true;
        }
        // 找到中间节点
        ListNode fast = A;
        ListNode slow = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        // 从中间节点往后反转
        // 当slow走到尾节点时，就可以不必再继续了
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        // 开始遍历回文
        // 这里不要用fast，因为fast可能不在尾节点
        while (A != slow) {
            if (A.val != slow.val) {
                return false;
            }
            // 当链表长度为偶数时，会出现一种情况（后面细说）
            if (A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next; 
        }
        return true;
    }
}

反转也不能写成下面这样：

    while (slow.next != null) {
            ListNode cur = slow.next;
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

上面的代码会陷入死循环。因为在最后修改了 slow 的位置，变成了 cur，所以 slow.next 是指向的位置是原来的 slow 。因此最终就陷入了死循环。如下图：

最后，我们会发现其实改来改去最终都在兜圈子。

综上本题来看，难度确实是挺大的，要注意的细节也是挺多的，无愧于字节跳动的秋招笔试题。

牛客网——链表分割

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：既然要分割链表，那我们直接按照原来的链表顺序遍历，把小于 x 的节点放到小链表中，其余节点放到大链表中。

我们就会不假思索的写出下面的代码：

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // 这题比较虾仁猪心：思路简单，但细节很多
        // 如果链表为空或者链表只有一个节点，就直接返回该节点
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        // 为了更为方便，我们定义头节点和尾节点
        ListNode beforeStart = null;
        ListNode beforeEnd = null;
        ListNode afterStart = null;
        ListNode afterEnd = null;
        // 遍历链表，小于放一边，大于放一边，然后小的串大的
        while (pHead != null) {
            if (pHead.val < x) {
                // 尾插到小链表中
                if (beforeStart == null) {
                    beforeStart = pHead;
                    beforeEnd = pHead;
                } else {
                    beforeEnd.next = pHead;
                    beforeEnd = beforeEnd.next;
                }
            } else {
                // 尾插到大链表中
                if (afterStart == null) {
                    afterStart = pHead;
                    afterEnd = pHead;
                } else {
                    afterEnd.next = pHead;
                    afterEnd = afterEnd.next;
                }
            }
            pHead = pHead.next;
        }
        beforeEnd.next = afterStart;
        return beforeStart;
    }
}

但上面的代码在测试的时候，会抛出空指针异常。其实就是当小链表为空（链表中所有的值均大于 x）时，这个 beforeStart 为空，那么去访问其 next 值时，就会发生空指针异常。因此，当小链表为空时，直接返回大链表，当大链表为空时，直接返回小链表即可。但很遗憾，又出现了死循环的问题：如下图所示：

因此，我们还得把 afterEnd 的 next 置为null。通过一系列的纠正，最终的代码如下：

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // 这题比较虾仁猪心：思路简单，但细节很多
        // 如果链表为空或者链表只有一个节点，就直接返回该节点
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        // 为了更为方便，我们定义头节点和尾节点
        ListNode beforeStart = null;
        ListNode beforeEnd = null;
        ListNode afterStart = null;
        ListNode afterEnd = null;
        // 遍历链表，小于放一边，大于放一边，然后小的串大的
        while (pHead != null) {
            if (pHead.val < x) {
                // 尾插到小链表中
                if (beforeStart == null) {
                    beforeStart = pHead;
                    beforeEnd = pHead;
                } else {
                    beforeEnd.next = pHead;
                    beforeEnd = beforeEnd.next;
                }
            } else {
                // 尾插到大链表中
                if (afterStart == null) {
                    afterStart = pHead;
                    afterEnd = pHead;
                } else {
                    afterEnd.next = pHead;
                    afterEnd = afterEnd.next;
                }
            }
            pHead = pHead.next;
        }
        
        // 把小链表和大链表串起来
        if (beforeEnd == null) {
            // 如果小链表为空，那么就直接返回大链表
            // 那么大链表就是按照原来链表的顺序，即无需将最后节点的next置为null
            return afterStart;
        }
        if (afterStart == null) {
            return beforeStart;
        }
        beforeEnd.next = afterStart;
        afterEnd.next = null;
        return beforeStart;
    }
}

这题虽然思路简单，但要注意的细节很多，稍一疏忽，就会犯错。简直就是：虾仁猪心。

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

思路：两个链表相交，有一个特点就是：相交之后的链表长度一定是相同的。假设前面不相交的长度是想等的，定义一个 cur1 指向一个链表，定义一个 cur2 指向另一个链表，去遍历两个链表，当两者不相等时，就一直遍历，直至相等为止。但遗憾的是两者长度会出现不一样的情况，这里依然是使用快慢指针的方法。当长度不相等时，就让长度长的链表先走两者的差值步数，然后再一起走，那么最终的结果一定是两者一起走到相等或者两者走到都为 null。最终的步骤：

1、先算出两者的长度，求其长度差。

2、再让长度长的链表走长度差步

3、接着两者一起走，判断是否相等

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先算出各自长度，让长的链表走两者长度的差值步，再一起走，如果相遇则其相交。
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int len1 = 0;
        int len2 = 0;
        while (cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            len2++;
            cur2 = cur2.next;
        }
        if (len1 > len2) {
            // 让headA走差值步
            cur1 = headA;
            cur2 = headB;
            int len = len1 - len2;
            while (len-- > 0) {
                cur1 = cur1.next;
            }
            // 开始比较
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            // 走到这里，有两种情况：1、cur1与cur2 都为空了，跳出了循环
            // 2、两者确实是相遇了。 我们只需判断一下即可
            if (cur1 == null) {
                return null;
            }
            // 其实这里不判断，也可以运行通过，因为题目要求不相遇就返回null，
            // 而比较到null时，cur1也是null，所以返回cur1也是对的（碰巧）。
            return cur1;
        }else {
            // 让headB走差值步
            cur1 = headA;
            cur2 = headB;
            int len = len2 - len1;
            while (len-- > 0) {
                cur2 = cur2.next;
            }
            // 开始比较
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            // 走到这里，有两种情况：1、cur1与cur2 都为空了，跳出了循环
            // 2、两者确实是相遇了。 我们只需判断一下即可
            if (cur1 == null) {
                return null;
            }
            // 其实这里不判断，也可以运行通过，因为题目要求不相遇就返回null，
            // 而比较到null时，cur1也是null，所以返回cur1也是对的（碰巧）。
            return cur1;
        }
    }
}

上面的代码在后面一起走的部分中大部分代码是一致的，因此就可以简化为下面这样：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先算出各自长度，让长的链表走两者长度的差值步，再一起走，如果相遇则其相交。
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int len1 = 0;
        int len2 = 0;
        while (cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            len2++;
            cur2 = cur2.next;
        }
        // 假设headA为长链表
        int len = len1-len2;
        cur1 = headA;
        cur2 = headB;
        if (len < 0) {
            // 说明headB是长链表
            len = - len;
            cur1 = headB;
            cur2 = headA;
        }
        // 走到这里，长链表一定已经确定了
        while (len-- > 0) {
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        if (cur1 == null) {
            return null;
        }
        return cur1;
    }
}

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

思路：快慢指针。当一个链表没有环，那么肯定是快指针先走到终点，如果一个链表有环，则快指针会先入环，接着慢指针再入环，最终快慢指针会相遇（一定是快指针走两步，慢指针走一步，这样快指针才不会包含慢指针）。如果快指针走三步，就有可能出现慢指针一直在快指针中间的情况。

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 如果链表为空或者链表的第一个节点的next为空，则说明没有成环
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 快指针如果遇到结尾的情况就可以停止了
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 一定要走完才能判断
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

其实，我们仔细观察会发现：在快指针还没开始走的时候，while循环的判断条件和前面的if判断条件是一样的，都是判断链表是否为空或者是链表的第一个节点的 next 值是是否为空。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 快指针如果遇到结尾的情况就可以停止了
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 一定要走完才能判断
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

思路：这个题目的意思就是让我们找到链表的第一个成环的节点。如下图所示：

上面那种情况只是我们认为的理想情况：慢指针入环时，快指针刚好只走完一圈，但是实际走完几圈我们是不确定的，因此可以设 n 为快指针走的圈数，带入求解的结果就是：x = n*m - y = (n-1)*m + (m-y)，最终结果还是我们前面的结论。因为 (n-1)只是圈数，最终还是会停在这个相遇点。

这里最重要的是抓住：快指针走的路程是慢指针的两倍。

1、找到相遇点

2、慢指针从头走，快指针从相遇点走，都以相同的速度。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 找到相遇点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            // 相遇就停下来
            if (slow == fast) {
                break;
            }
        }
        // 链表里没有环的情况有几种：
        if (fast != slow || head == null || head.next == null) {
            // 说明没有环
            return null;
        }
        // slow从链表头开始走，fast从相遇点开始走
        slow = head;
        while (slow != fast) {
            fast = fast.next;
            slow =slow.next;
        }
        return slow;
    }
}

因为这里在相遇之后，还要执行代码，就必须要判断链表是否为空和只有一个节点无环的情况。

好啦！本期数据结构之链表的经典笔试题的学习之旅就到此结束啦！我们下一期再一起学习吧！