Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1436480
  • 博文数量: 241
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-11 22:27
个人简介

--

文章分类

全部博文(241)

文章存档

2021年(3)

2019年(6)

2018年(1)

2017年(9)

2016年(21)

2015年(50)

2014年(125)

2013年(26)

我的朋友

分类: C/C++

2013-09-27 15:15:04

一、若链表为双向链表。
    就像一根不均匀的香找出中间位置,从两头开始烧。同理,设置一个头指针,一个尾指针,头指针往后移动,尾指针往前移动。移动到什么时候是中间位置呢?这就要分两种情况了:
(1)链表长度是偶数,此时中间位置是,头指针、尾指针分别指向对方,则中间位置就是头尾指针了。
(2)链表长度是奇数,此时投尾指针指向相同,中间位置也就是指向相同的节点。


二、若链表不是双向链表(单向链表)。    
    此时思路类似于O(n)求解链表的倒数K节点,就是使用快慢指针,慢指针指向链表开头,快指针指向慢指针后第K节点(如果链表长度有大于K的节点数),如果快指针没到链表尾节点,快慢指针都后移一个节点,当快指针到尾节点,此时慢指针指向倒数K的节点。
    所以,以此类推,单向链表的中间节点的求法就是:慢指针每次移动一个节点,快指针每次移动两个节点(当然,慢指针移动2个节点,快指针移动4个节点可行吗?),此时,又分为以下两种情况:
(1)链表长度是偶数,快指针下一个节点为NULL,此时慢指针指向节点以及下一个节点为中间节点。
(2)链表长度是奇数,快指针指向NULL,此时中间结点就是慢指针指向的节点(慢指针先移动,快指针后移动)。
阅读(1398) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~