免费注册建网站,专业做网站官网,返佣网站都是自己做的,土特产直营网站建设代码3道链表力扣题 一、删除链表中的节点#x1f30f; 题目链接#x1f4d5; 示例#x1f340; 分析#x1f4bb; 代码 二、反转链表#x1f30f; 题目链接#x1f4d5; 示例#x1f340; 分析① 递归② 迭代 三、判断一个链表是否有环#x1f30f; 题目链接#x1f4d5; … 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;}
}完整代码
