剑指Offer-从尾到头打印链表

2017/3/9 posted in  算法-数据结构  

输入一个链表,从尾到头打印链表每个节点的值。

问题解答

要解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可是输出的要求顺序却是从尾到头。也就是说第一个遍历到的节点,最后一个输出,而最后一个遍历到的节点第一个输出。这就是典型的后进先出,我们可以用栈实现这个顺序。每经过一个节点的时候,把该节点放入到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出节点的值,此时,输出的节点顺序已经反转过来了。
既然可以使用栈实现这个需求,那么我们就可以考虑使用递归,递归本质上就是一个栈结构。这样要实现反过来输出链表,我们每访问到一个结点的时候,先递归输出它后面的节点,在输出该节点自身,这样链表的输出就反过来了。

递归实现

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    private ArrayList<Integer> array = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        search(listNode);
        return array;
    }
    public void  search(ListNode listNode){
        if(listNode != null){
            search(listNode.next);
            array.add(listNode.val);
        }
        
    }
}

本题基于递归实现看起来很简洁,但是有个问题,当链表非常长的时候,就会导致函数调用层级很深,从而有可能导致函数调用栈溢出。

显示栈实现

import java.util.*;

public class Solution {
    
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        while(listNode != null){
            stack.offerFirst(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> array = new ArrayList<>(stack.size());
        while (stack.size()>0) {
            array.add(stack.pollFirst());
        }
        return array;
    }
    
}

翻转链表

如果可以改变原链表的结构,就可以对链表进行翻转。

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