剑指Offer - 从尾到头打印链表(Java实现)

题目链接：https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&&tqId=11156&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一： 翻转链表：首先我们新创建一个结点作为翻转之后的头结点，然后我们遍历原来的链表，使用头插法将当前结点插入新的链表中，这样我们就得到了一个翻转之后的链表，然后将头结点后移及翻转成功，然后遍历新的链表，将当前结点添加到链表的尾部。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode newListNode = new ListNode(0);
        ListNode nextNode = null;
        while(listNode != null) {
            nextNode = listNode.next;
            listNode.next = newListNode.next;
            newListNode.next = listNode;
            listNode = nextNode;
        }
        newListNode = newListNode.next;
        ArrayList<Integer> ans = new ArrayList<>();
        while(newListNode != null) {
            ans.add(newListNode.val);
            newListNode = newListNode.next;
        }
        return ans;
    }
}

  思路二： 的 函数

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> ans = new ArrayList<>();
        while(listNode != null) {
            ans.add(0, listNode.val);
            listNode = listNode.next;
        }
        return ans;
    }
}

  思路三：递归：从头结点开始，一直递归到最后一个结点，当返回的时候向 中添加元素

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

  思路四： 工具类的 函数

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> ans = new ArrayList<>();
        while(listNode != null) {
            ans.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(ans);
        return ans;
    }
}

  思路五： 栈的应用

/**
*    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> ans = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        while(listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while(!stack.empty()) {
            ans.add(stack.pop());
        }
        return ans;
    }
}