剑指offer 面试题05

朱雀 2022-03-22 07:47 290阅读 0赞

题目：输入个链表的头结点，从尾到头反过来打印出每个结点的值。

一般来说翻转过来打印链表中的值，应该不允许修改原链表的内容，由于顺序读取数据，打印是从尾到头，有种后进先出的感觉，很容易就能想到通过栈的方法来实现。

再引申一步，递归实际上也是一个栈的思想，所以也可以通过递归的方式来实现。

下面是代码：

package partOne;
    
    import java.util.Stack;
    
    public class PrintLinkNode {
        private static class LinkNode{
            int data; //节点的数据
            LinkNode nextLinkNode; //下一个节点
        }
    
        //采用栈的方式实现
        private void printLinkNodeByStack(LinkNode linkNode)
        {
            if(linkNode==null){
                return;
            }
    
            Stack<LinkNode> stackList = new Stack<>();
            LinkNode pNode = linkNode;
            while (pNode!=null){
                stackList.push(pNode);
                pNode = pNode.nextLinkNode;
            }
    
            LinkNode temNode;
            while (!stackList.isEmpty()){
                temNode = stackList.pop();
                System.out.println("栈节点值是："+temNode.data);
            }
    
        }
    
        //采用递归的方式实现
        private void printLinkNodeByRecursion(LinkNode linkNode){
            if(linkNode!=null){
                if(linkNode.nextLinkNode!=null){
                    printLinkNodeByRecursion(linkNode.nextLinkNode);
                }
            }
            System.out.println("递归节点值是："+linkNode.data);
        }
    
        public static void main(String[] args) {
            LinkNode rootNode = new LinkNode();
            rootNode.data=1;
            rootNode.nextLinkNode = new LinkNode();
            rootNode.nextLinkNode.nextLinkNode = new LinkNode();
            rootNode.nextLinkNode.nextLinkNode.nextLinkNode = new LinkNode();
            rootNode.nextLinkNode.nextLinkNode.nextLinkNode.nextLinkNode = new LinkNode();
            rootNode.nextLinkNode.data=2;
            rootNode.nextLinkNode.nextLinkNode.data=3;
            rootNode.nextLinkNode.nextLinkNode.nextLinkNode.data=4;
            rootNode.nextLinkNode.nextLinkNode.nextLinkNode.nextLinkNode.data=5;
    
            LinkNode pNode = rootNode;
            while (pNode!=null){
                System.out.println("原链表值："+pNode.data);
                pNode = pNode.nextLinkNode;
            }
    
            new PrintLinkNode().printLinkNodeByStack(rootNode);
            new PrintLinkNode().printLinkNodeByRecursion(rootNode);
        }
    
    }

输出结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcnJ5cHR0ZXI_size_16_color_FFFFFF_t_70][]

github代码地址：[代码地址][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhcnJ5cHR0ZXI_size_16_color_FFFFFF_t_70]: /images/20220322/6239a727122d400b9dfe8867e2223109.png
[Link 1]: https://github.com/harrypitter/Offer.git