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

题目描述

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

输入描述:

输入为链表的表头

输出描述:

输出为需要打印的“新链表”的表头

反转链表

首先我们想到的就是反转链表了,如果把链表反转了，然后再返回头，这样再次遍历的时候就相当于从尾到头打印了。

但是修改输入数据真的可行么？

剑指Offer中为我们在面试中提出了如下小提示

在面试时候，如果我们打算修改输入的数据，最好先问问面试官是不是允许修改

通常打印只是一个只读操作，我们肯定不希望输入时候修改链表的内容

如果要求反转的话，直接头插法就可以了

实现思路

package main

import (
4"fmt"
)

type NodeList struct {
    Val int
    Next *NodeList
}

// 不修改输入数据，只从尾到头打印链表
func printListFromTailToHead(head *NodeList) {
    if head != nil {
        printListFromTailToHead(head.Next)
        fmt.Printf("%d ->", head.Val)
    }
}

func main() {
    n3 := &NodeList(3, nil)
    n2 := &NodeList(2, n3)
    n1 := &NodeList(1, n2)
    
    fmt.Printf("\n NodeList 1 -> 2 -> 3 \n")
    
    //test
    fmt.Printf("\n Output: ")
    printListFromTailToHead(n1)
    fmt.Printf("\n \n")
}