【剑指offer】面试题6：从头到尾打印链表

野性酷女 2022-06-12 02:15 121阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

输入一个链表，从尾到头打印链表每个节点的值。链表节点的定义如下：

class ListNode {
        
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }

## 思路 ##

方法1：放到LinkedList中再打印出来（一起入栈然后出栈）  
方法2：遍历链表的时候将指针的指向反转（但是会修改输入的数据）  
我们采用方法1实现  
（提交代码忘了import java.util.Collections;给我挂了一次，心痛！！）

## 代码 ##

public static class ListNode {
        int val;
        public ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }   
    
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        ListNode current = listNode;
        while(current != null) {
            arrayList.add(current.val);
            current = current.next;
        }
        Collections.reverse(arrayList);
        return arrayList;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    /**
     * 功能测试
     * 1.链表有多个节点
     * 2.链表只有一个节点
     */
    private static void test1() {
        ListNode head1 = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        head1.next = node1;
        node1.next = node2;
        node2.next = node3;
        ArrayList<Integer> arr1 = new ArrayList<>(Arrays.asList(4,3,2,1));
        ArrayList<Integer> arr2 = _06_PrintListInReversedOrder.printListFromTailToHead(head1);
        MyTest.equal(arr1.equals(arr2), true);
    
        ListNode head2 = new ListNode(99);
        ArrayList<Integer> arr3 = new ArrayList<>(Arrays.asList(99));
        ArrayList<Integer> arr4 = _06_PrintListInReversedOrder.printListFromTailToHead(head2);
        MyTest.equal(arr3.equals(arr4), true);
    }
    
    /**
     * 特殊输入测试
     * 输入的链表头结点为null
     */
    private static void test2() {
        ArrayList<Integer> arrayList = new ArrayList<>();
        ArrayList<Integer> arr2 = _06_PrintListInReversedOrder.printListFromTailToHead(null);
        MyTest.equal(arrayList.equals(arr2), true);
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews