从单个链表中提取中间元素 [英] 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屋！