从尾到头打印链表 -- java

题目描述

输入链表的第一个节点，从尾到头反过来打印出每个结点的值。

链表节点定义如下：

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
    ListNode(){}
}

解题思路使用头插法将链表反转

当链表反转过后，每个节点的值就可以从头到尾输出了。

PS：在面试中，如果我们打算修改输入的数据，则最好先问面试官是否允许修改。

使用栈

每经过一个节点的时候，把该节点放到栈中。当遍历完整个链表后，再从栈顶开始逐个输出节点的值。

使用递归

递归在本质上就是一个栈结构。我们每次访问到一个节点，先递归输入它后面的节点，在输入该节点本身。

PS：当链表非常长的时候，就会导致函数的层级很深，从而有可能导致栈溢出。

使用 Collections.reverse()

从头到尾遍历链表，每次访问到一个节点，将值取出放入ArrayList，然后利用Collections.reverse()将数组的值反转。

java代码使用头插法将链表反转

简单来说，就是不断将原先链表的节点依次插入在虚拟头节点head和头节点后面一个节点之间。

根据上面的图片来思考代码，要仔细看箭头指向。

实际例子：

初始head变量时，它指向null。
在图片第一行让1指向null(也就是head所指向的节点)，让head指向1；
在图片第二行要让2放在head和1之间，需要先让2指向1(也就是head所指向的节点)，接着让head指向2；
在图片第三行要让3放在head和2之间，需要先让3指向2(也就是head所指向的节点)，接着让head指向3；
以此类推…

分析出规律得到伪代码思路（让a指向b的意思就是a.next = b）：

遍历所有Node节点，假设当前节点变量名是listNode，需要先让listNode指向head.next，接着让head指向listNode，最后让listNode=listNode.next来遍历下一个节点，直到listNode为空，此时遍历结束。

代码：

public class PrintListReversingly {
    // 从尾到头打印链表
    public static void printListReversingly_headInsert(ListNode listNode) {
        if(listNode == null) {
            return;
        }

        ListNode head = new ListNode();
        while (listNode != null) {
            // 临时变量保存下一个节点
            ListNode temp = listNode.next;
            // 让当前节点指向 head指向的节点
            listNode.next = head.next;
            // 让head指向当前节点
            head.next = listNode;
            // 遍历下一个节点
            listNode = temp;
        }
        // 将反转后的节点放入结果中
        while ((head = head.next) != null) {
            System.out.print(head.val + " ");
        }
    }

    // 测试
    public static void main(String[] args) {
        ListNode listNode_1 = new ListNode(1);
        ListNode listNode_2 = new ListNode(2);
        ListNode listNode_3 = new ListNode(3);

        listNode_1.next = listNode_2;
        listNode_2.next = listNode_3;

        // 反转前
        print_listNode(listNode_1);
        System.out.println();

        // 反转后
        printListReversingly_headInsert(listNode_1);
        System.out.println();
    }

    // 打印listNode
    public static void print_listNode(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }
}

使用栈

import java.util.Stack;

public class PrintListReversingly {
    // 从尾到头打印链表
    public static void printListReversingly_stack(ListNode listNode) {
        if(listNode == null) {
            return;
        }

        Stack stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode);
            listNode = listNode.next;
        }

        while (!stack.isEmpty()) {
            System.out.print(stack.pop().val + " ");
        }
    }

    // 测试
    public static void main(String[] args) {
        ListNode listNode_1 = new ListNode(1);
        ListNode listNode_2 = new ListNode(2);
        ListNode listNode_3 = new ListNode(3);

        listNode_1.next = listNode_2;
        listNode_2.next = listNode_3;

        // 反转前
        print_listNode(listNode_1);
        System.out.println();

        // 反转后
        printListReversingly_stack(listNode_1);
        System.out.println();
    }

    // 打印listNode
    public static void print_listNode(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }
}

使用递归

public class PrintListReversingly {
    // 从尾到头打印链表
    public static void printListReversingly_recursively(ListNode listNode) {
        if (listNode != null) {
            if (listNode.next != null) {
                printListReversingly_Recursively(listNode.next);
            }
            System.out.print(listNode.val + " ");
        }
    }
        // 测试
    public static void main(String[] args) {
        ListNode listNode_1 = new ListNode(1);
        ListNode listNode_2 = new ListNode(2);
        ListNode listNode_3 = new ListNode(3);

        listNode_1.next = listNode_2;
        listNode_2.next = listNode_3;

        // 反转前
        print_listNode(listNode_1);
        System.out.println();

        // 反转后
        printListReversingly_recursively(listNode_1);
        System.out.println();
    }

    // 打印listNode
    public static void print_listNode(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }
}

使用 Collections.reverse()

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class PrintListReversingly {
    // 从尾到头打印链表
    public static void printListReversingly_collections(ListNode listNode) {
        ArrayList result = new ArrayList<>();
        while (listNode != null) {
            result.add(listNode);
            listNode = listNode.next;
        }
        Collections.reverse(result);
        for (ListNode a_result : result) {
            System.out.print(a_result.val + " ");
        }
    }

    // 测试
    public static void main(String[] args) {
        ListNode listNode_1 = new ListNode(1);
        ListNode listNode_2 = new ListNode(2);
        ListNode listNode_3 = new ListNode(3);

        listNode_1.next = listNode_2;
        listNode_2.next = listNode_3;

        // 反转前
        print_listNode(listNode_1);
        System.out.println();

        // 反转后
        printListReversingly_collections(listNode_1);
        System.out.println();
    }

    // 打印listNode
    public static void print_listNode(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.val+" ");
            listNode = listNode.next;
        }
    }
}

来自
《剑指offer》
Coding-Interviews/从尾到头打印链表.md at master · todorex/Coding-Interviews

从尾到头打印链表 -- java

Java相关栏目本月热门文章