一、若链表为双向链表。
就像一根不均匀的香找出中间位置,从两头开始烧。同理,设置一个头指针,一个尾指针,头指针往后移动,尾指针往前移动。移动到什么时候是中间位置呢?这就要分两种情况了:
(1)链表长度是偶数,此时中间位置是,头指针、尾指针分别指向对方,则中间位置就是头尾指针了。
(2)链表长度是奇数,此时投尾指针指向相同,中间位置也就是指向相同的节点。
二、若链表不是双向链表(单向链表)。
此时思路类似于O(n)求解链表的倒数K节点,就是使用快慢指针,慢指针指向链表开头,快指针指向慢指针后第K节点(如果链表长度有大于K的节点数),如果快指针没到链表尾节点,快慢指针都后移一个节点,当快指针到尾节点,此时慢指针指向倒数K的节点。
所以,以此类推,单向链表的中间节点的求法就是:慢指针每次移动一个节点,快指针每次移动两个节点(当然,慢指针移动2个节点,快指针移动4个节点可行吗?),此时,又分为以下两种情况:
(1)链表长度是偶数,快指针下一个节点为NULL,此时慢指针指向节点以及下一个节点为中间节点。
(2)链表长度是奇数,快指针指向NULL,此时中间结点就是慢指针指向的节点(慢指针先移动,快指针后移动)。
阅读(1397) | 评论(0) | 转发(0) |