网站流量被用完了,怎样申请做p2p融资网站,服装设计是冷门专业吗,商城网站 免费开源文章目录 环形链表判断是否有环找出环的入口位置 双指针反转链表#xff08;Reverse a Linked List#xff09;移除链表中的指定元素#xff08;Remove Linked List Elements#xff09; 环形链表
判断是否有环
环形链表是指链表中的某些节点的 next 指针指向了链表中的某… 文章目录 环形链表判断是否有环找出环的入口位置 双指针反转链表Reverse a Linked List移除链表中的指定元素Remove Linked List Elements 环形链表
判断是否有环
环形链表是指链表中的某些节点的 next 指针指向了链表中的某个前面的节点导致链表中的节点构成一个环。
思路快慢指针Floyd 判圈算法
我们可以使用 快慢指针 来判断链表中是否有环。这种方法也叫做 Floyd 判圈算法是一个经典且高效的解法。
• 快指针slow pointer 每次移动一步。
• 慢指针fast pointer 每次移动两步。
判断条件
如果链表中没有环快指针最终会遇到 null这时候说明链表没有环。如果链表有环快指针和慢指针一定会相遇因为快指针每次移动两步而慢指针每次移动一步快指针追得上慢指针。 // 判断 是否有环public boolean hasCycle(ListNode head) {ListNode slow head;ListNode fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {return true;}}return false;}找出环的入口位置
一旦我们知道链表有环下一步就是 找到环的入口。这可以通过以下的步骤来实现
思路
1. 判断环的存在首先使用快慢指针来判断链表是否有环如果没有环则直接返回 null。
2. 找到环的入口
• 假设链表有环快慢指针在环内相遇。
• 将其中一个指针从头节点开始另一个指针保持在相遇位置。
• 然后两个指针同时每次移动一步。它们相遇的位置就是环的入口。
为什么能这么做
• 假设链表总共有 n 个节点其中前 k 个节点在环外后 n-k 个节点在环内。
• 当快慢指针在环内相遇时假设慢指针在环内相遇的位置是 X。
• 如果将其中一个指针移回链表的起点并让两个指针同时移动每次移动一步它们必定会在环的入口相遇。
public ListNode detectCycle(ListNode head) {ListNode slow head;ListNode fast head;// 1. 判断有没有环while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) { // 快慢指针相遇说明有环break;}}// 如果没有环直接返回 nullif (fast null || fast.next null) {return null;}// 2. 找到环的入口fast head; // 快指针移到链表头while (slow ! fast) {slow slow.next;fast fast.next;}return slow; // 返回环的入口
}双指针
反转链表Reverse a Linked List
反转链表是链表操作中最经典的题目之一特别是在面试中经常出现。这个问题的基本要求是将链表的节点顺序反转。
基本思路
使用三个指针来反转链表
1. prev指向当前节点的前一个节点。
2. cur指向当前节点。
3. next指向当前节点的下一个节点。
我们遍历链表将每个节点的 next 指针指向前一个节点。 public ListNode reverseList(ListNode head) {ListNode prev null;ListNode curr head;ListNode next null;while (curr ! null) {next curr.next;curr.next prev;prev curr;curr next;}return prev;}移除链表中的指定元素Remove Linked List Elements
值得注意移除元素需要保留该节点的前一个节点。 public ListNode removeElements(ListNode head, int val) {while (head ! null head.val val) {head head.next;}ListNode curr head;ListNode prev null;while (curr ! null) {if (curr.val val) {prev.next curr.next;curr prev.next;}else {prev curr;curr curr.next;}}return head;}
