【3】3道链表力扣题：删除链表中的节点、反转链表、判断一个链表是否有环

一、删除链表中的节点

🌏 题目链接

【删除链表中的节点】https://leetcode.cn/problems/delete-node-in-a-linked-list/description/

📕 示例

🖊 输入： head = [4, 5, 1, 9], node = 5
🖊 输出： [4, 1, 9]
🖊 解释： 指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

🖊 输入： head = [4, 5, 1, 9], node = 1
🖊 输出： [4, 5, 9]
🖊 解释： 指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

🍀 分析

public class ListNode {int val;ListNode next;ListNode(int x) {val = x;}
}

🖊 每一个节点就是一个 ListNode 对象
🖊 val 属性存储了具体的数据
🖊 next 属性存储了一个节点的内存地址

public class Solution {public void deleteNode(ListNode node) {}
}

🖊 deleteNode(ListNode node) 方法中，参数node是要被"删除"的节点
🖊 在该题中能够获得到的已知条件就只有这个要被删除的节点 node

🖊 已知： 要被删除的节点 node
🖊 根据已知可以得到： ① 要被删除的节点往后的所有节点 node.next.next...（这里就考虑它的下一个节点 node.next）；② 可以得到节点的 val 和 node

---

🖊 这里的删除第三个节点，并不是把该节点从内存中移除，而是让第三个节点的值不再是【1】，而是它的下一个节点的值【9】。并且第三个节点的 next 存储它的下一个节点的 next

💻 代码

class Solution {public void deleteNode(ListNode node) {// 用被删除节点的下一个节点的值覆盖被删除节点的值node.val = node.next.val;// 被删除节点的next指向它下一个节点的nextnode.next = node.next.next;}
}

二、反转链表

🌏 题目链接

【206.反转链表】https://leetcode.cn/problems/reverse-linked-list/description/

📕 示例

🖊 输入： head = [1, 2, 3, 4, 5]
🖊 输出： [5, 4, 3, 2, 1]

🖊 输入： head = [1, 2]
🖊 输出： [2,1]

🖊 输入： head = []
🖊 输出： []

🍀 分析

class Solution {public ListNode reverseList(ListNode head) {}
}

🖊 reverseList(ListNode head) 方法只有一个参数 head（头指针），它指向了头节点

① 递归

👆 如上图所示，假如 reverseList 方法编写成功的话，reverseList(head) 方法调用后，该链表的头指针会指向方法调用之前的尾节点（如上图的 newHead）
👆 原本的 head = [5, 4, 3, 2, 1] 也变成了 head = [1, 2, 3, 4, 5]

🖊 假如 reverseList(head.next) 调用成功，则整个链表如上图所示

---

---

public class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;// 递归ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

② 迭代

🖊 已知条件就只有一个头指针 head，只能通过这个 head 进行反转

---

public class Solution {/*** 头插法（迭代）*/public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode newHead = null;do {ListNode tmp = head.next;head.next = newHead;newHead = head;head = tmp;} while (head != null);return newHead;}
}

三、判断一个链表是否有环

🌏 题目链接

141.判断一个链表是否有环：https://leetcode.cn/problems/linked-list-cycle/description/

📕 示例

🍀 分析

🖊 使用快慢指针思想完成
🖊 fast 指针每次 next 两步；slow 指针每次 next 一步。若有环的话，快慢指针必然相遇
🖊 如果 fast 指向 null 或 fast.next 指向 null，则链表没有环

💻 代码

public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) return false;ListNode slow = head;ListNode fast = head.next;// 【fast == null || fast.next == null】都代表链表无环while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) return true;}return false;}
}

🍀 完整代码