赞
踩
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表是以结点的方式存储的,是链式存储。结点可以在运行时动态生成。链表是有序的列表,但其在内存中的存储是非连续、非顺序的。
在链表数据结构中,我们把一个数据元素的存储映像称为结点(Node)。而一个结点包含存储数据元素的两部分信息:数据域(Data)和指针域(Next)。
数据域:存储数据元素信息的域;
指针域:存储直接后继位置的域,指向下一个结点。
head.next表示为头结点head的后继结点;而head则为head.next的前驱结点。
public static int getLength(HeroNode head){
if(head.next == null){
return 0; // 空链表
}
int length = 0;
HeroNode cur = head.next;
while (cur != null) {
length++;
cur = cur.next; //遍历
}
return length;
}
/* 思路:①编写一个方法,接收head结点,同时接收一个index ②index表示倒数第index个结点 ③先把链表从头到尾遍历,得到链表的总长度 getLength ④得到size后,从链表的第一个结点开始,遍历(size-index)个,就可以得到 ⑤找到,则返回该结点,否则返回null */ public static HeroNode findLastIndexNode(HeroNode head, int index){ //判断链表为空,返回null if (head.next == null) { return null; //没找到 } //第一个遍历得到链表的长度(结点个数) int size = getLength(head); //第二次遍历size-index位置,就是倒数第index个结点 //先做一个index的校验 if (index <= 0 || index > size) { return null; } HeroNode cur = head.next; for(int i = 0; i < size-index; i++){ cur = cur.next; } return cur; }
/*
思路:①先定义一个结点reverseHead = new HeroNode();
②从头到尾遍历原来的链表,每遍历一个结点,就将其取出,并放在新链表的最前端
③将原来的链表的head.next = reverseHead.next
*/
public static void reverseList(HeroNode head){
//如果当前链表为空,或者只有一个结点,无需反转直接返回
if
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。