从尾到头打印链表

题目：

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

class ListNode{

​ int value;

​ ListNode next;

}

分析：

​ 因为链表只能从头开始遍历，所以正向打印链表很容易，如果需要反向打印，是一种先进后出的结构，可以考虑使用“栈”这种结构。

ListNode.java

public class ListNode {

    int value;
    ListNode next;

    public ListNode() {

    }

    public ListNode(int value) {
        this.value = value;
    }
}

测试用例：

@Test
public void test1() {
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);
    ListNode node5 = new ListNode(5);
    ListNode node6 = new ListNode(6);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node6;

    PrintListReverse.printListByStack(node1);
    PrintListReverse.printListByRecursive(node1);
    PrintListReverse.printListByArray(node1);
    PrintListReverse.printListByReverse(node1);
}

方案一：

使用栈来反向输出链表

/**
 * 使用栈反向输出链表
 * @param node
 */
public static void printListByStack(ListNode node) {
    Stack<Integer> stack = new Stack<>();

    while (null != node) {
        stack.push(node.value);
        node = node.next;
    }

    while (!stack.isEmpty()) {
        System.out.println(stack.pop() + ", ");
    }
}

方案二：

使用递归逆序打印，先输出后一个，在输出前一个

/**
  * 使用递归逆序打印
  * @param node
  */
public static void printListByRecursive(ListNode node) {

    if (null != node) {
        if (null != node.next) {
            printListByRecursive(node.next);
        }
        System.out.print(node.value + ", ");
    }else{
        System.out.println("无效的链表");
    }
}

方案三：

将链表中的元素放到list集合中，然后倒序输出

/**
 * 使用list集合反向输出
 * @param node
 */
public static void printListByArray(ListNode node) {
    List<Integer> numList = new ArrayList<>();

    while (node != null) {
        numList.add(node.value);
        node = node.next;
    }

    if (numList.isEmpty()) {
        System.out.println("链表无效");
        return;
    }

    for (int i = numList.size() -1; i >=0; i--) {
        System.out.print(numList.get(i) + ", ");
    }
}

方案四：

反转链表，然后按正常顺序输出

public static void printListByReverse(ListNode node) {
    // 反转链表
    ListNode reverse = reverse(node);

    while (reverse != null) {
        System.out.print(reverse.value + ", ");
        reverse = reverse.next;
    }
}

/**
 * 反转链表
 */
public static ListNode reverse(ListNode head) {
	// 如果没有下一个元素，说明是尾结点
    if (head.next == null) {
        return head;
    }
 
    // 不断递归，直到到达尾结点 6，6=head.next，head=5
    ListNode reverseListNode = reverse(head.next);
    // 把尾结点的前一个节点当做尾结点的下一个节点 6->5
    head.next.next = head;
    // 断开尾结点的上一个节点到它下个节点的引用，断开 5->6
    head.next = null;
    return reverseListNode;
}