首页 > 编程知识 正文

快慢指针原理,快慢指针判断回文

时间:2023-05-06 10:43:08 阅读:195040 作者:1551

快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。
快慢指针的应用
判断单链表是否为循环链表
让快慢指针从链表头开始遍历,快指针向前移动两个位置,慢指针向前移动一个位置;如果快指针到达NULL,说明链表以NULL为结尾,不是循环链表。如果 快指针追上慢指针,则表示出现了循环。
fast=slow=head;
fast=fast->next->next;
slow=slow->next;
while(true){
if (fastNULL || fast->nextNULL)
return false;
else if (fastslow || fast->nextslow)
return true;
else{
fast=fast->next->next;
slow=slow->next;
}
}
在有序链表中寻找中位数
该方法在不借助计数器变量实现寻找中位数的功能。原理是:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素,当快指针移动x次后到达表尾(1+2x),说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点(因为快指针再移动一次就超过了范围,所以已经移步动了),说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。
while (fast&&slow)
  {
  if (fast->nextNULL)
  return slow ->data;
  else if (fast->next != NULL && fast->next->next NULL)
  return (slow ->data + slow ->next->data)/2;
  else
  {
  fast= fast->next;
  fast= fast->next;
  slow = slow ->next;
  }
  }

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。