从尾到头打印链表

Wu Jun 2020-01-14 21:28:22
01 数据结构与算法 > 算法题 > 链表

题目出处

从尾到头打印链表

1 题目描述

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

2 解题思路

最直接的思路是反转链表,但是通常打印是个只读操作,不希望打印时修改内容。

思路一:使用栈

遍历链表的顺序是从头到尾,可输出的顺序却是从尾到头,典型的“后进先出”,可以使用栈来实现。栈具有后进先出的特点,在遍历链表时将值按顺序放入栈中,最后出栈的顺序即为逆序。

Java中的 Stack 类已过时,队列 LinkedList 效率不高,栈和队列首选 ArrayDeque。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*/
import java.util.ArrayList;
import java.util.ArrayDeque ;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()){
            result.add(stack.pop());
        }
        return result;
    }
}

思路二:使用递归

递归的本质就是一个栈结构,所以也能使用递归来实现。

要实现反过来输入链表,每访问到一个节点的时候,先递归输出它后面的节点,再输出该节点自身

有个问题:当链表非常长的时候,递归会导致函数调用的层级很深,有可能导致栈溢出。

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

思路三:使用头插法

头插法顾名思义是将节点插入到头部:在遍历原始链表时,将当前节点插入新链表的头部,使其成为第一个节点。

为了能将一个节点插入头部,我们引入了一个叫头结点的辅助节点,该节点不存储值,只是为了方便进行插入操作。不要将头结点与第一个节点混起来,第一个节点是链表中第一个真正存储值的节点。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode tempHead = new ListNode(-1);
        while (listNode != null) {
            ListNode nextHead = listNode.next;
            listNode.next = tempHead.next;
            tempHead.next = listNode;
            listNode = nextHead;
        }
        
        ArrayList<Integer> result = new ArrayList<>();
        ListNode head = tempHead.next;
        while (head != null) {
            result.add(head.val);
            head = head.next;
        }
        return result;
    }
}