数据结构-单链表进阶之快慢指针原理（快速查找法）

àì夳堔傛蜴生んèń 2022-05-25 06:48 117阅读 0赞

面试题：快速找到未知长度单链表的中间节点？

这个问题的解决方法分为普通方法和高级方法。

1.普通方法即我们大家都能一下子想到的，首先遍历一遍获取总长度L，然后再次遍历循环至L/2即可；时间复杂度为：

O(L+L/2)=O(3/2L)

代码简单实现：

typedef struct {
    	int data;
    	LNode *next;
    }LNode,*LinkList;
    
    /*
    function:普通方法
    首先遍历一遍获取总长度L，然后再次遍历循环至L/2即可
    */
    LNode *getElement(LinkList L) {
    	if (L == NULL) {
    		return NULL;
    	}
    	int i = 1;
    	LNode *p = L->next;
    	while (p!=NULL)
    	{
    		p = p->next;
    		i++;
    	}
    	
    	int j = 1;
    	int mid = i / 2;
    	LNode *midNode = L->next;
    	while (j<mid)
    	{
    		midNode = midNode->next;
    	}
    	return midNode;
    }

2.高级方法：快慢指针法，设置2个指针\*faster，\*mid都指向单链表的头节点，其中faster移动的速度为mid的2倍，当faster移动到末尾，mid即在中间位置了，以下是简单实现:

/*
    function:快速查找未知长度单链表中间节点
    快慢指针法
    */
    LNode *fasterGetElement(LinkList L) {
    	LNode *mid, *faster;
    	mid = L->next;
    	faster = L->next;
    	while (faster!=NULL)
    	{
    		mid = mid->next;
    		//faster = faster->next->next
    		faster = faster->next;
    		faster = faster->next;
    	}
    	return mid;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读

相关用快慢指针实现查找链表的中间值

慢指针就是类似于合并排序过程中的步长那样一个指针每次走二一个走以等走到一半时第一个刚完基于此提高效率 package com.linkedlist; ...

ゝ一世哀愁。/ 2024年04月18日 17:04/ 0 赞/ 34 阅读

相关快慢指针法判断链表是否有环

快慢指针的初始值均设为head，每次移动慢指针一步，移动快指针两步。循环的条件为快指针不为null且快指针的next不为null。每次移动后判断快指针和慢指针是否相等，

￡神魔★判官ぃ/ 2024年02月20日 11:56/ 0 赞/ 5 阅读

相关链表的快慢指针：查找中点

一直做题都是数组中点，直接算n/2，但是链表的中点怎么求出来，我还真没见过，只能说自己做题太少了。今天做leetcode上的题就遇到了，虽然说简单，但对我来说这是个新的知识点，

野性酷女/ 2022年09月25日 13:22/ 0 赞/ 115 阅读

相关 LeetCode 环形链表【快慢指针】

1 题目描述给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数

灰太狼/ 2022年09月09日 15:50/ 0 赞/ 153 阅读

相关线性表(插入/清除数据/快慢指针查找中间数据)

1.概念线性表：顺序存储结构线性表及链式存储结构线性表链式存储结构线性表（线性链表）：具有链接存储结构的线性表，它用一组地址任意的存储单元存放线性表中的数据

╰半夏微凉°/ 2022年06月17日 06:08/ 0 赞/ 210 阅读

相关【java数据结构与算法学习】快慢指针---快速找到未知长度单链表的中间节点

如题：快速找到未知长度单链表的中间节点第一种方法是大多人都能想到的方法：先遍历整个链表得到链表的长度，然后遍历链表的一半，找到链表的中间节点。此操作的时间复杂度是O(n)+

青旅半醒/ 2022年05月31日 13:41/ 0 赞/ 102 阅读

相关数据结构-单链表进阶之快慢指针原理（快速查找法）

面试题：快速找到未知长度单链表的中间节点？这个问题的解决方法分为普通方法和高级方法。 1.普通方法即我们大家都能一下子想到的，首先遍历一遍获取总长度L，然后再次遍历循环至

àì夳堔傛蜴生んèń/ 2022年05月25日 06:48/ 0 赞/ 118 阅读

相关数据结构-链表之单链表

单链表即每个节点都存在数据域和指针域（特殊节点除外），每个节点都一个直接前驱节点和直接后继节点（头节点无前驱，尾节点无后继），简单来说就是上一个节点的指针域中存放了下一

╰+攻爆jí腚メ/ 2022年05月25日 05:20/ 0 赞/ 279 阅读

相关用快慢指针原理得到单链表中间结点的数据

普通方法是遍历一遍得到表长，再根据此值移到中间快慢指针的方法可以提高效率，当快指针以两倍速度到达表尾时慢一些的指针刚好在中间结点 include<stdio.h

不念不忘少年蓝@/ 2022年05月20日 07:39/ 0 赞/ 136 阅读

相关快慢链表和快慢指针

> 腾讯的一道面试题：如何快速找到位置长度单链表的中间节点？普通方法，就是先遍历，在从头找到2/length的中间节点。算法复杂度是：O(3\n/2)。而更快的方法就是利用快慢

阳光穿透心脏的1/2处/ 2022年05月16日 01:28/ 0 赞/ 155 阅读