双指针的应用

前言

昨天刷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

写在后面

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