从尾到头打印链表

4.从尾到头打印链表

题目描述

从尾到头反过来打印出每个结点的值。

如：
input:

graph LR
1-->2
2-->3

output:

3,2,1

解题思路

1. 递归实现

要实现逆序打印链表 1->2->3;可以使用使用递归，先将链表看做当前节点和右侧节点两部分；如：1->(2->3),先打印右侧节点,再打印当前节点：右侧节点也可以看做两部分如：(2)->(3),也是先打印当前节点的右侧节点，在打印当前节点；如此递归，可实现逆序打印。

代码实现

java 代码

    /**
     * 单向链表节点
     * @param <T>
     */
    class LinkedNode<T extends Object>{
        private T value;
        private LinkedNode<T> next;

        public T getValue() {
            return value;
        }

        public void setValue(T value) {
            this.value = value;
        }

        public LinkedNode<T> getNext() {
            return next;
        }

        public void setNext(LinkedNode<T> next) {
            this.next = next;
        }
    }
    /**
     * 反向打印链表
     * @param node 链表首节点
     * @return
     */
    private ArrayList<Integer> printReverseLink( LinkedNode<Integer> node) {
        ArrayList<Integer>  list = new ArrayList();
        if (node!=null){
            list.addAll(printReverseLink(node.next));
            list.add(node.value);
        }
        return list;
    }

    public static void main(String[] args){
        LinkedNode<Integer> first = new LinkedNode<>();
        first.setValue(1);
        LinkedNode<Integer> two = new LinkedNode<>();
        two.setValue(2);
        LinkedNode<Integer> three = new LinkedNode<>();
        three.setValue(3);
        two.setNext(three);
        first.setNext(two);
        System.out.println(printReverseLink(first));
    }

Kotlin 代码

    /**
     * 单向链表节点
     */
    data class LinkedNode<T : Any?>(var value: T) {
        var next: LinkedNode<T>? = null
    }

    /**
     * 反向打印链表
     * @param node 链表首节点
     * @return
     */
    private fun printReverseLink(node: LinkedNode<Int>?):ArrayList<Int> {
        val list = ArrayList<Int>()
        if (node!=null){
            list.addAll(printReverseLink(node.next))
            list.add(node.value)
        }
        return list
    }
    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val first = LinkedNode(1)
        first.next = LinkedNode(2)
        first.next?.next = LinkedNode(3)
        print(printReverseLink(first))
    }

2. 使用头插法

头插法顾名思义是将节点插入到头部：在遍历原始链表时，将当前节点插入新链表的头部，使其成为第一个节点。

链表的操作需要维护后继关系，例如在某个节点 node1 之后插入一个节点 node2，我们可以通过修改后继关系来实现：

node3 = node1.next;
node2.next = node3;
node1.next = node2;

为了能将一个节点插入头部，我们引入了一个叫头结点的辅助节点，该节点不存储值，只是为了方便进行插入操作。不要将头结点与第一个节点混起来，第一个节点是链表中第一个真正存储值的节点。

graph LR
1-->2
2-->3

引入head节点

graph LR
head

循环遍历链接，插入头结点后

node=1

graph LR
head-->1

node=2

graph LR
head-->2
2-->1

node=3

graph LR
head-->3
3-->2
2-->1

代码实现

java 代码

    /**
     * 头插法实现反向打印链表
     * 
     * @param node 链表首节点
     * @return
     */
    private ArrayList<Integer> printReverseLinkToHead(LinkedNode<Integer> node) {
        LinkedNode<Integer> head = new LinkedNode<>();
        head.setValue(-1);
        while (node != null) {
            LinkedNode<Integer> next = node.getNext();
            node.setNext(head.getNext());
            head.setNext(node);
            node = next;
        }
        ArrayList<Integer> list = new ArrayList();
        head = head.getNext();
        while (head != null) {
            list.add(head.getValue());
            head = head.getNext();
        }
        return list;
    }

    public static void main(String[] args){
        LinkedNode<Integer> first = new LinkedNode<>();
        first.setValue(1);
        LinkedNode<Integer> two = new LinkedNode<>();
        two.setValue(2);
        LinkedNode<Integer> three = new LinkedNode<>();
        three.setValue(3);
        two.setNext(three);
        first.setNext(two);

        System.out.println(printReverseLinkToHead(first));
    }

Kotlin 代码

    /**
     * 使用头插法反向打印链表
     * @param node 链表首节点
     * @return
     */
    private fun printReverseLinkToHead(node: LinkedNode<Int>?):ArrayList<Int> {
        var currentNode = node
        var head:LinkedNode<Int>? = LinkedNode(-1)
        while (currentNode!=null){
            val next = currentNode.next
            currentNode?.next = head!!.next
            head!!.next = currentNode
            currentNode = next
        }
        val list = ArrayList<Int>()
        head = head!!.next
        while (head!=null){
            list.add(head.value)
            head = head.next
        }
        return list
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val first = ListNode(1)
        first.next = ListNode(2)
        first.next?.next = ListNode(3)
        print(printReverseLinkToHead(first))
    }

3. 使用栈来实现

栈的规则时后进先出，则可以将链表遍历存放到栈中，然后在出栈则出栈顺序就是反向打印链表

代码实现

java 代码

    /**
     * 使用栈实现反向打印链表
     *
     * @param node 链表首节点
     * @return
     */
    private ArrayList<Integer> printReverseLinkToHeadWithStack(LinkedNode<Integer> node){
        Stack<Integer> stack = new Stack<>();
        while (node != null) {
            stack.add(node.getValue());
            node = node.next;
        }
        ArrayList<Integer> list = new ArrayList();
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    public static void main(String[] args){
        LinkedNode<Integer> first = new LinkedNode<>();
        first.setValue(1);
        LinkedNode<Integer> two = new LinkedNode<>();
        two.setValue(2);
        LinkedNode<Integer> three = new LinkedNode<>();
        three.setValue(3);
        two.setNext(three);
        first.setNext(two);

        System.out.println(printReverseLinkToHeadWithStack(first));
    }

Kotlin 代码

    /**
     * 使用栈反向打印链表
     * @param node 链表首节点
     * @return
     */
    private fun printReverseLinkToHeadWithStack(node: LinkedNode<Int>?): ArrayList<Int> {
        val stack = Stack<Int>()
        var current = node
        while (current != null) {
            stack.push(current.value)
            current = current.next
        }
        val list = ArrayList<Int>()
        while (!stack.empty()) {
            list.add(stack.pop())
        }
        return list
    }

    /**
     * 入口函数
     */
    fun main(args: Array<String>) {
        val first = ListNode(1)
        first.next = ListNode(2)
        first.next?.next = ListNode(3)
        print(printReverseLinkToHeadWithStack(first))
    }

引用声明

该题目引用自
牛客网