剑指 Offer 06. 从尾到头打印链表

in with 0 comment

剑指 Offer 06. 从尾到头打印链表

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

示例 1:

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

解法思路

  1. 遍历链表得出长度,新建数据,再次遍历链表将链表前面的元素放到数组的后边
  2. 将该题看为一个栈进行递归,先进栈,出栈就可反转链表。递归时记录链表长度,节点为 null 时 return new int[count],出递归时往数组里塞值,下标为数据长度 - 当前下标

代码

解法一

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        int count = 0;
        ListNode node = head;
        while (node != null) {
            count++;
            node = node.next;
        }
        int[] result = new int[count];
        node = head;
        for (int i = count - 1; i >= 0; --i) {
            result[i] = node.val;
            node = node.next;
        }
        return result;
    }
}
返回该题

解法二

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    public int[] reversePrint(ListNode head) {
        return recuv(head, 0);
    }

    public int[] recuv(ListNode node, int index) {
        if (node == null) return new int[index];
        int[] result = recuv(node.next, ++index);
        result[result.length - index] = node.val;
        return result;
    }
}