剑指Offer06. 从尾到头打印链表

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

JAVA代码(完整的四种方法)

做一道题很容易，但是如何多种方式解决问题，多种角度思考问题，才能更加锻炼我们的逻辑思维能力。

倒序插入

获取链表长度创建数组，将链表从头遍历，倒序插入数组。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        ListNode p = head;
        int len = getLength(head);
        int[] arr = new int[len];
        int index = len-1;
        while(index>=0){
    
            arr[index] = p.val;
            p = p.next;
            index--;
        }
        return arr;
    }
    
    //获取链表长度
    public int getLength(ListNode head){
    
        ListNode p = head;
        int n = 0;
        while(p!=null){
    
            p = p.next;
            n++;
        }
        return n;
    }
}

栈方法

将链表入栈，再出栈放入数组中。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        Stack<Integer> stack = new Stack<Integer>();
        ListNode p = head;
        while(p!=null){
    
            stack.push(p.val);
            p = p.next;
        }
        int size = stack.size();
        int[] arr = new int[size];
        for(int i = 0;i<size;i++){
    
            arr[i] = stack.pop();
        }
        return arr;
    }
}

逆转链表法

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        //将链表逆置
        ListNode p = head;
        if(p==null){
    
            return new int[0];
        }
        ListNode q = p.next;
        int len = 1;
        while(q!=null){
    
        	//保存下一个操作的结点
            ListNode next = q.next;
            q.next = p;
            p = q;
            q = next;
            len++;
        }
        //处理尾结点
        head.next = null;

        int[] arr = new int[len];
        ListNode l = p;
        int index = 0;
        while(l!=null){
    
            arr[index++] = l.val;
            l = l.next;
        }
        return arr;
    }

    
}

ArrayList法

将链表数据存到ArrayList中，再逆序放到数组中

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public int[] reversePrint(ListNode head) {
    
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListNode p = head;
        int n = 0;
        while(p!=null){
    
            list.add(p.val);
            p = p.next;
            n++;
        }
        int[] arr = new int[n];
        for(int i = 0;i<n;i++){
    
            arr[i] = list.get(n-i-1);
        }
        return arr;
    }
}