首页 > 代码库 > 快慢指针实现不依赖计数器寻找中位数(linked list)

快慢指针实现不依赖计数器寻找中位数(linked list)

该方法在不借助计数器变量实现寻找中位数的功能。原理是:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素,当快指针移动x次后到达表尾(1+2x),说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。
while (fast&&slow) 
  { 
  if (fast->next==NULL) 
  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; 
  } 
  }

快慢指针实现不依赖计数器寻找中位数(linked list)