【原】410，剑指 Offer-从尾到头打印链表

数据结构和算法 2023-06-10 发布于上海

展开全文

Every strike brings me closer to the next home run.

每一次挥棒落空都让我更接近下一个全垒打。

问题描述

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

示例 1：

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

限制：

0 <= 链表长度 <= 10000

链表节点类

1public class ListNode {
2    int val;
3    ListNode next;
4
5    ListNode(int x) {
6        val = x;
7    }
8}

使用栈来解决

从尾到头打印链表，首先这个链表是单向的，如果是双向的，直接从后往前打印就行了，这里链表不是单向的。

这里最容易想到的一种方式就是把链表的节点全部压栈，因为栈是先进后出的一种数据结构，全部压栈之后再一个个出栈即可，

压栈完之后再一个个出栈

 1public int[] reversePrint(ListNode head) {
 2    Stack<ListNode> stack = new Stack<>();
 3    ListNode temp = head;
 4    while (temp != null) {
 5        stack.push(temp);
 6        temp = temp.next;
 7    }
 8    int size = stack.size();
 9    int[] res = new int[size];
10    for (int i = 0; i < size; i++) {
11        res[i] = stack.pop().val;
12    }
13    return res;
14}

递归方式解决

我们知道如果逆序打印一个链表使用递归的方式还是很简单的，像下面这样

1public void reversePrint(ListNode head) {
2    if (head == null)
3        return;
4    reversePrint(head.next);
5    System.out.println(head.val);
6}

但这里实际上是要我们返回逆序打印的结果，也就是返回一个数组，所以我们可以改一下

 1public int[] reversePrint(ListNode head) {
 2    int cout = length(head);
 3    int[] res = new int[cout];
 4    reversePrintHelper(head, res, cout - 1);
 5    return res;
 6}
 7
 8//计算链表的长度
 9public int length(ListNode head) {
10    int cout = 0;
11    ListNode dummy = head;
12    while (dummy != null) {
13        cout++;
14        dummy = dummy.next;
15    }
16    return cout;
17}
18
19public void reversePrintHelper(ListNode head, int[] res, int index) {
20    if (head == null)
21        return;
22    reversePrintHelper(head.next, res, index - 1);
23    res[index] = head.val;
24}

先反转再打印

关于链表的反转其实解法也比较多，这里先列出简单的两种，一个是递归的，一个是非递归的。

递归的方式

1public ListNode reverseList(ListNode head) {
2    if (head == null || head.next == null)
3        return head;
4    ListNode tempList = reverseList(head.next);
5    head.next.next = head;
6    head.next = null;
7    return tempList;
8}

非递归的方式

 1public ListNode reverseList(ListNode head) {
 2    ListNode pre = null;
 3    while (head != null) {
 4        ListNode next = head.next;
 5        head.next = pre;
 6        pre = head;
 7        head = next;
 8    }
 9    return pre;
10}