3 剑指offer--链表--从尾到头打印链表

链表--从尾到头打印链表（剑指 LeetCode）

基础知识

链表应该是面试时被提及最频繁的数据结构。链表的结构很简单，它由指针把若干个节点连接成链状结构。链表的创建、插入节点、删除节点等操作都只需要20行左右的代码就能实现，其代码量比较适合面试。

链表是一种动态数据结构，是因为在创建链表时，无须知道链表的长度。当插入一个节点时，我们只需要为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表当中。内存分配小是在创建链表时一次性完成的，而是每添加- • 个节点分配一次内存。由于没有闲置的内存,链表的空间效率比数组高。

由于链表中的内存不是一次性分配的，因而我们无法保证链表的内存和数组一样是连续的。因此，如果想在链表中找到它的第i个节点，那么我们只能从头节点开始，沿着指向下一个节点的指针遍历链表，它的时间效率为0( N )。而在数组中，我们可以根据下标在0(1)时间内找到第i个元素。下面是在链表中找到第一个含有某值的节点并删除该节点的代码;

问题

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

通常，这种情况下，我们不希望修改原链表的结构。返回一个反序的链表，这就是经典的“后进先出”，我们可以使用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，给一个新的链表结构，这样链表就实现了反转。

看到这道题后，很多人的第一反应是从头到尾输出将会比较简单，于是我们很自然地想到把链表中链接节点的指针反转过来，改变链表的方向，然后就可以从头到尾输出了。但该方***改变原来链表的结构。是否允许在打印链表的时候修改链表的结构？这取决于面试官的要求，因此在面试的时候我们要询问清楚面试官的要求

但有一个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用桟溢出。显然用桟基于循环实现的代码的鲁棒性要好一些。更多关于循环和递归的

讨论，

代码

用栈

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> returnList = new ArrayList<>();
        if(listNode == null){
            return returnList;
        }
        Stack<ListNode> stacks = new Stack<>();
        while(listNode != null){
            stacks.push(listNode);
            listNode = listNode.next;
        }
        while(!stacks.isEmpty()){
            returnList.add(stacks.pop().val);
        }
        return returnList;
    }
}

用队列

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> addressArrayList = new ArrayList<Integer>();
    if(listNode == null){
        ArrayList first = new ArrayList();
        return first;
    }
    while (listNode != null) {
        addressArrayList.add(listNode.val);
        listNode = listNode.next;

    }

    Collections.reverse(addressArrayList);
    return addressArrayList;
}

递归

import java.util.ArrayList;

public class Solution {

    ArrayList<Integer> arrayList = new ArrayList<Integer>();

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null)
            return arrayList;
        printListFromTailToHead(listNode.next);
        arrayList.add(listNode.val);
        return arrayList;
    }
}

LeetCode

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

方法一：迭代

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}