双指针的应用

前言

昨天刷python面试宝典的链表题的时候发现了双指针方法,在进行寻找链表中间节点和判定列表是否有环的时候逻辑清晰效率也比较高.所以在这里记录一下

链表中间节点

有链表如下:


1.PNG

定义双指针slow和fast


2.PNG

两指针有以下规则

1.两指针初始节点都为head
2.slow为慢指针即每次移动1个节点,fast为快指针即每次移动2个节点
遵循以上规则移动图如下:


3.PNG

结论:

当快指针走到链表结尾时,慢指针一定是在链表的中间节点。
当链表长度为奇数时,慢指针指向的正好是中间节点;当链表长度为偶数时,慢指针当前节点和下一节点都是链表的中间节点

代码实现

class LNode:
    def __new__(self,x):
      self.data=x
      self.next=None
def find_middle_node(head):
  if head is None or head.next is None:
    return head
  fast = head
  slow = head
  slowPre = head
  while fast is not None and fast.next is None:
    slowPre = slow
    slow = slow.next
    fast = fast.next.next
slowPre.next = None
return slow

写在后面

链表是否有环的逻辑也是相同:
指针规则相同的情况下快慢指针同时向后走,如果快指针撞到了慢指针那就说明链表有环,如果快指针走到底也没有撞到慢指针那说明链表无环.

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1.返回链表的中间节点 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回...
    zhtttyi阅读 1,495评论 0 0
  • 什么是快慢指针:快慢指针是链表操作中的常用操作,最经典的应用是判断单链表中是否有环。 判断单链表是否存在环 两个指...
    YocnZhao阅读 3,633评论 0 8
  • 双指针算法 ​ 双指针包括快慢指针和左右指针。快慢指针一般用来对链表进行操作,比如判断链表是否有环、寻...
    LJH_9442阅读 1,794评论 0 0
  • LeetCode原题链接[https://leetcode-cn.com/problems/linked-list...
    LittleBoy丶阅读 5,551评论 0 2
  • 快慢指针主要解决的问题: 寻找/删除第K个节点; 有关链表环问题解法:寻找/删除第K个节点。 问题一: 给定任意一...
    Arthurcsh阅读 3,165评论 0 1