【剑指Offer】03——从尾到头打印链表 （链表）

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

解题思路

一种方法是利用栈来实现；
另外一种方法是利用三个指针把链表反转，关键是 r 指针保存断开的节点。

file

参考代码

Java

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

    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            if (listNode == null)
                return new ArrayList<Integer>();
            ListNode head = listNode;          // 记住头部
            ListNode cur = listNode.next;
            // 指针反转，并走到最后
            while (cur != null) {
                ListNode temp = cur.next; // 保存下一个ListNode
                cur.next = head; // 指针反转
                head = cur; // 下一个指针
                cur = temp;
            }
            // 此时listNode 的next还指向第二个node，所以要让ListNode.next = null, 防止循环
            listNode.next = null;
            ArrayList<Integer> res = new ArrayList<Integer>(); // 返回结果
            while (head != null) {
                res.add(head.val);
                head = head.next;
            }
            return res;
        }
    }

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        if listNode is None:
            return []
        head = listNode
        cur = listNode.next
        while cur is not None:
            temp = cur.next
            cur.next = head
            head = cur
            cur = temp
        listNode.next = None
        res = []
        while head is not None:
            res.append(head.val)
            head = head.next
        return res

个人订阅号

image