【go写数据结构】练习--快速找到未知长度的单链表的中间节点

刺骨的言语ヽ痛彻心扉 2022-12-12 04:53 91阅读 0赞

git地址：https://gitee.com/HappyTeemo/go\_for\_algorithm

/** 题目 快速找到未知长度的单链表的中间节点 解决思路 （一）使用一个指针，先索引一遍获取总长度，再取长度一半去循环获取到中间值 算法复杂度：O(L)+O(L/2) = O(3L/2) （二）使用两个指针，快指针和慢指针，快指针一次向前走2格，慢指针一次走一格，当快指针走完全程，慢指针正好走在中间 算法复杂度：O(L/2) */
    
    func (l *LinkList) FindMidEle(e *ElemType) int { 
    	//search是快指针，middle是慢指针
    	search := l.Head
    	middle := l.Head
    
    	i := 0
    	for search != nil { 
    		if search.Next != nil { 
    			//快指针是慢指针的两倍速度
    			search = search.Next.Next
    			middle = middle.Next
    		} else {  //是针对奇数个元素，再次进行操作，是之能够退出
    			search = search.Next
    			middle = middle.Next //奇数需要再次向后取一位，才会到达中间
    		}
    		i++
    	}
    	*e = middle.Data
    	return i
    }
    
    func (l *LinkList) Test1() { 
    	my_list := new(LinkList)
    	my_list.InitList()
    
    	for i := 1; i <= 11; i++ { 
    		my_list.ListInsert(i, ElemType(i*i+1))
    		my_list.Echo()
    	}
    	var e ElemType
    	index := my_list.FindMidEle(&e)
    	fmt.Println("中间值:", e, "位置", index)
    }

发表评论取消回复

表情：

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

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

相关阅读

相关【go写数据结构】练习--快速找到未知长度的单链表的中间节点

git地址：https://gitee.com/HappyTeemo/go\_for\_algorithm / 题目快速找到未知长度的单链表的中间节点解决思路（

刺骨的言语ヽ痛彻心扉/ 2022年12月12日 04:53/ 0 赞/ 92 阅读

相关【go写数据结构】线性表-链表实现

git地址：https://gitee.com/HappyTeemo/go\_for\_algorithm package my_list impo

柔光的暖阳◎/ 2022年12月12日 04:53/ 0 赞/ 185 阅读

相关【go写数据结构】线性表-双向链表

git地址：https://gitee.com/HappyTeemo/go\_for\_algorithm package my_list impo

红太狼/ 2022年12月12日 04:52/ 0 赞/ 216 阅读

相关数据结构 -- 单链表之删除节点

1. 单链表的创建 2.单链表的节点的删除以下代码在 vs2010 测试通过： include "stdafx.h" include <stdlib.

向右看齐/ 2022年09月20日 15:03/ 0 赞/ 187 阅读

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

有道算法面试题：快速找到未知长度单链表的中间节点。你可以普通方法也可用比较好的方法，去解决这个问题。由于单链表不知道长度，必须遍历完整个单链表才知道单恋表的长度，然后根

你的名字/ 2022年06月02日 06:16/ 0 赞/ 173 阅读

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

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

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

相关快慢指针（找未知长度链表的中间、判断链表是否是循环链表）

`快慢指针也是一个可以用于很多问题的技巧。所谓快慢指针中的快慢指的是指针向前移动的步长，每次移动的步长较大即为快，步长较小即为慢，常用的快慢指针一般是在单链表中让快指针每次向前

心已赠人/ 2022年05月17日 02:07/ 0 赞/ 124 阅读

相关单链表的操作：节点查找、节点插入、节点删除、求单链表长度

本节讲解一下单链表中节点的查找、插入、删除、求单链表长度等操作。按序号查找结点值在单链表中从第一个结点出发，顺指针next

╰半夏微凉°/ 2022年02月20日 01:49/ 0 赞/ 377 阅读

相关【数据结构】带头节点的单链表逆置

include<iostream> using namespace std; typedef struct LNode { int da

川长思鸟来/ 2021年12月04日 05:37/ 0 赞/ 316 阅读

相关查找单链表的中间节点

这是今天面试测开面试官提到的一个问题，当时有点紧张，代码写的不整洁，回来整理了一下。个人有点强迫症，纸上的代码一定想用机器跑起来。特整理如下：问题描述：查找单链表的中间节

雨点打透心脏的1/2处/ 2021年09月26日 15:38/ 0 赞/ 310 阅读