复习：数据结构-链表题

移除链表元素

力扣题目 203. 移除链表元素

给你一个链表的头节点 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

思路

我们先使用1 3 2 3，移除元素 3

如果是使用C/C++的话记得释放内存，否则可能会占用一些内存空间。

难点：

因为单链表的性质，只能指向下一个节点，刚才我们删除的是中间和尾部的节点，如果删除的是头节点呢？我们该如何处理？

删除链表节点的两种方式：

• 在原表上进行操作。
• 新建一个虚拟头节点进行操作。

这里，我就使用第二种方法吧，方便操作，不需要更多的逻辑设置。

例如：

首先新建一个虚拟头节点（dummy）指向当前链表的头部（head），然后在进行删除操作即可，最后记得返回的是 dummy.next。

/**  
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**  
     * @param head 链表的头节点
     * @param val  需要移除的节点的值
     * @return 移除指定值后的链表的头节点
     */
    public ListNode removeElements(ListNode head, int val) {
        // 如果头节点为空，则直接返回  
        if (head == null) {
            return head;
        }

        // 创建一个虚拟节点（dummy node），通常是一个不会出现在链表中的值
        // 虚拟节点的作用是方便处理头节点被移除的情况
        ListNode dummy = new ListNode(-1, head);
        // pre 指针用于遍历链表的前一个节点
        ListNode pre = dummy;
        // cur 指针用于遍历链表当前节点
        ListNode cur = head;

        // 当cur不为空时，继续遍历
        while (cur != null) {
            // 如果当前节点的值等于val
            if (cur.val == val) {
                // 将前一个节点的next指向当前节点的下一个节点
                pre.next = cur.next;
            } else {
                // 如果当前节点的值不等于val，则将pre指针移动到当前节点
                pre = cur;
            }
            // 移动cur到下一个节点
            cur = cur.next;
        }

        // 返回虚拟节点的下一个节点，即为移除指定值后的链表的头节点
        return dummy.next;
    }
}

反转链表

力扣题目 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

进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思路

我们无需再定义一个新的链表来实现翻转，只需要改变链表的next指针的指向，就可以在原有的链上直接进行翻转。

如图：

让我们来看看动画，翻转过程是如何进行的：

1. 我们定义了两个指针，一个是 cur，用于指向当前的节点，一个是 pre，用于指向 cur 的前一个节点。
2. 然后开始翻转了，先用一个tmp指针记录cur.next，然后改变cur指向pre，移动 pre 到 cur，移动 cur 到 下一个节点 tmp。
3. 接下来就是循坏的过程了，最后 cur 指向 null 时，循环结束，返回 pre 即可。

代码如下：

java
/**  
 * public class ListNode {  
 *     int val;  
 *     ListNode next;  
 *     ListNode() {}  
 *     ListNode(int val) { this.val = val; }  
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  
 * }  
 *
 *  
 * 思路：
 *
 * 使用三个指针，pre（前驱节点）、cur（当前节点）和tmp（临时节点），遍历链表并反转其指向。  
 * 初始时，pre 为 null，cur 为头节点 head。  
 * 在每次循环中，先将 cur 的下一个节点保存到 tmp 中，然后将 cur 的 next 指向 pre，  
 * 接着将 pre 和 cur 分别向前移动一个节点，即 pre = cur 和 cur = tmp。  
 * 循环结束后，pre 将成为反转后链表的头节点，返回 pre 即可。  
 *
 */  
class Solution {  
    public ListNode reverseList(ListNode head) {  
        // 如果头节点为空（链表为空），则直接返回  
        if (head == null){  
            return head;  
        }  
  
        // 前驱节点，初始为null  
        ListNode pre = null;  
        // 当前节点，初始为头节点  
        ListNode cur = head;  
        // 临时节点，用于保存当前节点的下一个节点  
        ListNode tmp = null;  
  
        // 当当前节点不为空时，进行循环  
        while(cur != null){  
            // 保存当前节点的下一个节点  
            tmp = cur.next;  
            // 将当前节点的 next 指向前驱节点，实现反转  
            cur.next = pre;  
            // 将前驱节点向前移动一个节点  
            pre = cur;  
            // 将当前节点向前移动一个节点  
            cur = tmp;  
        }  
  
        // 循环结束后，pre 指向反转后链表的头节点  
        return pre;  
    }  
}

环形链表 II

力扣题目 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 或者链表中的一个有效索引

进阶： 你是否可以使用 O(1) 空间解决此题？

思路

这道题主要考察的知识点有：

• 判断链表是否有环。
• 如何找到有环链表的入口。

这里呢，有两种解法：

• 哈希表法。
• 快慢指针法。

哈希表法：

我们遍历链表的每一个节点，并把它的节点记录下来，存到哈希表中。
当哈希表中存在某一个节点与当前节点相同时，就说明存在环，并且是环的入口，直接返回。

快慢指针法：

本作者感觉讲得不太好，关于数学的一些思维，大家可以看一下力扣大神的题解 环形链表 II（双指针，清晰图解）

下面是哈希表法的代码：

/**  
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 *
 * 给定一个单链表，检测链表中是否有环，并返回环的入口节点。
 * 如果链表中存在环，则返回环的入口节点；否则返回 null。
 */
public class Solution {
    /**  
     * @param head 链表的头节点
     * @return 环的入口节点，如果链表无环则返回 null
     */
    public ListNode detectCycle(ListNode head) {
        // 如果头节点为空，则直接返回  
        if (head == null) {
            return head;
        }

        // 定义一个当前节点指针，初始化为头节点  
        ListNode cur = head;

        // 创建一个集合，用于存储已经遍历过的节点  
        Set < ListNode > set = new HashSet < > ();

        // 遍历链表  
        while (cur != null) {
            // 如果当前节点已经在集合中出现过，说明有环，返回当前节点  
            if (set.contains(cur)) {
                return cur;
            } else {
                // 否则将当前节点加入集合  
                set.add(cur);
            }
            // 移动到下一个节点  
            cur = cur.next;
        }

        // 如果遍历完整个链表都没有环，则返回 null  
        return null;
    }
}