韦到头打印链表
题目描述
输入一个链表，从尾到头打印链表每个节点的值。
除非要通过索引频繁访问各个数据,不然大多数情况下都可以用链表代替数组.
链表部分主要要涉及:单链表,双端链表,有序链表,双向链表和有迭代器的链表(迭代器是用来随机访问链表元素的一种方法).
由于以前贪玩数据结构没上课,现在后悔所以要努力补上.
链结点:在 链表中,每个数据项都被包含在"链结点"(Link)中.一个链结点是某个类的对象,这个类可以叫Link.而每个Link对象中又包含着一个对下一个链 结点引用的字段(通常叫next).但是链表(LinkList)本身的对象中有一个字段(first)指向第一个链结点的引用.看图会清晰些.
这张表体现在代码里就两个构造类:
Link(链结点类)
输入描述:
输入为链表的表头
输出描述:
输出为需要打印的“新链表”的表头
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result=new ArrayList();
if(listNode==null)
return result;
Stack<ListNode> stack=new Stack();
stack.push(listNode);
while(listNode.next!=null)
{
stack.push(listNode.next);
listNode=listNode.next;
}
while(!stack.isEmpty())
{
ListNode node=stack.pop();
result.add(node.val);
}
return result;
}
}
链表结构之单链表
链表:一种数据存储结构.学链表首先要搞懂数组,按朋友的话说,数组和链表的关系就相当于QQ2008和QQ2009.除非要通过索引频繁访问各个数据,不然大多数情况下都可以用链表代替数组.
链表部分主要要涉及:单链表,双端链表,有序链表,双向链表和有迭代器的链表(迭代器是用来随机访问链表元素的一种方法).
由于以前贪玩数据结构没上课,现在后悔所以要努力补上.
链结点:在 链表中,每个数据项都被包含在"链结点"(Link)中.一个链结点是某个类的对象,这个类可以叫Link.而每个Link对象中又包含着一个对下一个链 结点引用的字段(通常叫next).但是链表(LinkList)本身的对象中有一个字段(first)指向第一个链结点的引用.看图会清晰些.
这张表体现在代码里就两个构造类:
Link(链结点类)
classLink{
publicintiData;
publicdoubledData;
publicLinknext;//这个next就是链结点对象对下个链接点的引用.默认初始化为NULL
publicLink(intid,doubledd){
iData=id;
dData=dd;
}
}
publicintiData;
publicdoubledData;
publicLinknext;//这个next就是链结点对象对下个链接点的引用.默认初始化为NULL
publicLink(intid,doubledd){
iData=id;
dData=dd;
}
}
LinkList(链表类)
classLinkList{
publicLinkfirst;//首链结点first,初始化为NULL
publicLinkList(){
first=null;
}
}
publicLinkfirst;//首链结点first,初始化为NULL
publicLinkList(){
first=null;
}
}
就这样一个链结点指向下个链结点的引用构成了整个链表.
今天这个实例,显示了一个单链表.主要的操作如下:
在链表头插入一个数据项.
在链表头删除一个数据项.
遍历链表显示内容.
首先插入一个链接点的逻辑就是:将first的引用指向Link对象链结点的next引用,然后再将first指向这个链结点就构造了新的链表.如图
代码大框如下:
今天这个实例,显示了一个单链表.主要的操作如下:
在链表头插入一个数据项.
在链表头删除一个数据项.
遍历链表显示内容.
首先插入一个链接点的逻辑就是:将first的引用指向Link对象链结点的next引用,然后再将first指向这个链结点就构造了新的链表.如图
代码大框如下:
publicvoidinsertFirst(intid,doubledd){
LinknewLink=newLink(id,dd);//构造新的链结点对象
newLink.next=first;//将链结点对象的next指向first的引用
first=newLink;//然后将first指向newLink对象
} 删 除一个链结点的逻辑就是:用一个临时变量存储first的引用(即要删除的链结点)然后将first指向first.next(即他只想的链结点对象的 next指向的那个链结点Link).这样要删除的那个链结点就没有了指针对他的引用.Java垃圾回收就会把他收回.实现了并返回存储的那个删除节点. 如图
代码大框如下:
LinknewLink=newLink(id,dd);//构造新的链结点对象
newLink.next=first;//将链结点对象的next指向first的引用
first=newLink;//然后将first指向newLink对象
} 删 除一个链结点的逻辑就是:用一个临时变量存储first的引用(即要删除的链结点)然后将first指向first.next(即他只想的链结点对象的 next指向的那个链结点Link).这样要删除的那个链结点就没有了指针对他的引用.Java垃圾回收就会把他收回.实现了并返回存储的那个删除节点. 如图
代码大框如下:
publicLinkdeleteFirst(){
Linktemp=first;//暂存first引用的这个链结点(即要删除的)
first=first.next;//将first指向他所引用的Link链接点的next引用
returntemp;//返回要删除的链结点
}
Linktemp=first;//暂存first引用的这个链结点(即要删除的)
first=first.next;//将first指向他所引用的Link链接点的next引用
returntemp;//返回要删除的链结点
}
这要弄清了,Java对象引用的关系理解起来就很容易了.下面就是实现的整个代码:
Code
打印的结果为:
List:(first--->last){88,88.88}{66,66.88}{44,44.88}{22,22.88}
{88,88.88}Deleted
{66,66.88}Deleted
{44,44.88}Deleted
{22,22.88}Deleted
List:(first--->last)
{88,88.88}Deleted
{66,66.88}Deleted
{44,44.88}Deleted
{22,22.88}Deleted
List:(first--->last)
继续扩展下添加查找对应键值和按对应键值删除链结点的find和delete方法.
find方法:
这个方法与上面的displayLink方法类似.将current定义为first,通过不断的current.next.iData与键值作比较,如果相等便返回当前引用.
如果一直到最后Null也没找到就返回Null
delete方法:
这个方法需要两个变量.current:当前链结点的引用 privious:前一链结点的引用.这个方法也是通过循环查找如果找到了
.就用前一引用的next指向当前的next的引用就可以了.见图
最后代码:
Code
执行结果:
List:(first--->last){88,88.88}{66,66.88}{44,44.88}{22,22.88}
theFindItem:{22,22.88}theDelItem:{22,22.88}
List:(first--->last){88,88.88}{66,66.88}{44,44.88} 优质内容筛选与推荐>>
1、解决 mysql error: Failed dependencies: 错误 分类： database 2013-09-11 11:23 772人阅读 评论(0) 收藏
2、Selenium 延时等待
3、BZOJ 2125 最短路
4、windows环境tomcat8配置Solr5.5.1
5、分享给有缘人——给明年依旧年轻的我们：欲望、外界、标签、天才、时间、人生目标、现实、懊悔、和经历
theFindItem:{22,22.88}theDelItem:{22,22.88}
List:(first--->last){88,88.88}{66,66.88}{44,44.88} 优质内容筛选与推荐>>
1、解决 mysql error: Failed dependencies: 错误 分类： database 2013-09-11 11:23 772人阅读 评论(0) 收藏
2、Selenium 延时等待
3、BZOJ 2125 最短路
4、windows环境tomcat8配置Solr5.5.1
5、分享给有缘人——给明年依旧年轻的我们：欲望、外界、标签、天才、时间、人生目标、现实、懊悔、和经历