题目描述

输入一个链表，从尾到头打印链表每个节点的值。

输入描述:

输入为链表的表头

输出描述:

输出为需要打印的“新链表”的表头

/**

*    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(链结点类)

class Link {

    public int iData;

    public double dData;

    public Link next; // 这个next就是链结点对象对下个链接点的引用.默认初始化为NULL

    public Link(int id, double dd){

        iData = id;

        dData = dd;

    }

}

LinkList(链表类)

class LinkList {

    public Link first; // 首链结点first,初始化为NULL

    public  LinkList () {

        first = null;

    }

}

就这样一个链结点指向下个链结点的引用构成了整个链表.

今天这个实例,显示了一个单链表.主要的操作如下:

在链表头插入一个数据项.

在链表头删除一个数据项.

遍历链表显示内容.

首先插入一个链接点的逻辑就是:将first的引用指向Link对象链结点的next引用,然后再将first指向这个链结点就构造了新的链表.如图

代码大框如下:

public void insertFirst(int id, double dd) {

    Link newLink = new Link(id, dd); // 构造新的链结点对象

    newLink.next = first; // 将链结点对象的next指向first的引用

    first = newLink;      // 然后将first指向newLink对象

}

删 除一个链结点的逻辑就是:用一个临时变量存储first的引用(即要删除的链结点)然后将first指向first.next(即他只想的链结点对象的 next指向的那个链结点Link).这样要删除的那个链结点就没有了指针对他的引用.Java垃圾回收就会把他收回.实现了并返回存储的那个删除节点. 如图

代码大框如下:

public Link deleteFirst() {

    Link temp = first; // 暂存first引用的这个链结点(即要删除的)

    first = first.next;// 将first指向他所引用的Link链接点的next引用

    return temp;       // 返回要删除的链结点

}

这要弄清了,Java对象引用的关系理解起来就很容易了.下面就是实现的整个代码:

打印的结果为:

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)

继续扩展下添加查找对应键值和按对应键值删除链结点的find和delete方法.

find方法:

这个方法与上面的displayLink方法类似.将current定义为first,通过不断的current.next.iData与键值作比较,如果相等便返回当前引用.

如果一直到最后Null也没找到就返回Null

delete方法:

这个方法需要两个变量.current:当前链结点的引用 privious:前一链结点的引用.这个方法也是通过循环查找如果找到了

.就用前一引用的next指向当前的next的引用就可以了.见图

最后代码:

执行结果:

List: (first ---> last){

88,88.88}{

66,66.88}{

44,44.88}{

22,22.88}

the Find Item: {

22,22.88}  the Del Item: {

22,22.88}

List: (first ---> last){

88,88.88}{

66,66.88}{

44,44.88}