从单个链接列表中提取中间元素 [英] Extract middle element from a single linked list

问题描述

我有一个问题：

从单个链接列表中查找中间元素。

Find the middle element from a single linked list.

我需要知道此问题的方式/方法。

I need to know the way/method of this problem.

推荐答案

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

You can use two pointers to iterate through the list - one which iterates twice as fast as the other. When the fast pointer reaches the end of the list then the slow pointer will be pointing at the mid-point.

算法：

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

这篇关于从单个链接列表中提取中间元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！