从单个链表中提取中间元素

Question

我有个问题:

从单个链表中查找中间元素.

我需要知道这个问题的方法/方法.

Answer 1

您可以使用两个指针迭代列表 - 一个迭代速度是另一个的两倍.当快速指针到达列表的末尾时,慢速指针将指向中间点.

算法:

init slow_pointer = head
init fast_pointer = head
repeat
   fast_pointer = fast_pointer->next;
   if fast_pointer == NULL
      break;
   fast_pointer = fast_pointer->next;
   if fast_pointer == NULL
      break;
   slow_pointer = slow_pointer->next;
until false
// slow_pointer now points at the middle node