数据结构--链表刷题(一)快慢指针

本文主要是介绍数据结构--链表刷题(一)快慢指针，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 1.快慢指针

  先看一道简单的题目：返回中间结点

这道题有一个最朴素的做法就是先遍历一边链表，设置计数器求出链表长度，再重新走1/2的链表长度，即可返回中间节点

        // 第二种解法  //这种解法需要遍历两次链表ListNode cur1 = head;int cnt = 0;while(cur1 != null) {cnt++;cur1 = cur1.next;}ListNode cur2 = head;cnt = cnt/2;while(cnt != 0) {cur2 = cur2.next;cnt--;}return cur2;

  但是这种方式有个明显的缺陷，就是你实际上是遍历了两遍链表，那有没有只遍历一次链表就能获得中间结点的方法呢？答案是有的，利用快慢指针

// 第一种解法  只需遍历一次链表ListNode slow = head,fast = head;while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}return slow;

快慢指针的核心思想其实是一种数学问题，即在相同时间内，路程之比就是速度之比 

「力扣」第 19 题： 倒数第 k 个结点 

 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 使用虚拟头节点 -- 能更好的处理删除头节点的问题ListNode dummyhead = new ListNode(0);dummyhead.next = head;ListNode slow = dummyhead;ListNode fast = dummyhead;while(n > 0) {fast = fast.next;n--;}while(fast.next != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyhead.next;}
}

一个小细节：如果不使用虚拟头节点  在删除头节点的过程中会出错 

2.判断是否带环

https://leetcode.cn/problems/linked-list-cycle/description/

代码实现：

1.快慢指针

public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null) return false;ListNode fast = head;ListNode slow = head;// 只要有环 则fast和slow一定会相遇while(fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if(fast == slow) return true;}return false;}
}

2.使用哈希表

public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> seen = new HashSet<ListNode>();while(head != null) {if(!seen.add(head)) {return true;}head = head.next;}return false;}
}

 2.环形链表的进阶

https://leetcode.cn/problems/linked-list-cycle-ii/submissions/

 

代码实现：

1.哈希表的实现
public class Solution {public ListNode detectCycle(ListNode head) {ListNode cur = head;Set<ListNode> seen = new HashSet<>();while(cur != null) {// 如果包含  则证明走到了入口点if(seen.contains(cur)) {return cur;}else {seen.add(cur);}cur = cur.next;}return null;}
}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(fast == slow) break;}// 跳出循环有两种conditionif(fast == null || fast.next == null) return null;// fast = head  两个指针一起走 直到相同fast = head;while(fast != slow) {fast = fast.next;slow = slow.next;}return slow;}
}

这篇关于数据结构--链表刷题(一)快慢指针的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---