面試：從尾到頭打印鏈表

題目：從尾到頭打印鏈表

要求：輸入一個鏈表的頭節點，從尾到頭反過來返回每個節點的值（用數組返回）。

示例：

`

輸入：head = [1,3,2]

輸出：[2,3,1]

`

限制：

0 <= 鏈表長度 <= 10000

題解1：遞歸法

因為是從尾到頭返回每一個節點的值，所以很容易想到如果從最後的節點將值放入數組中，然後再往前逐步將數據放入數組，最後回到頭節點返回即可，可以想到遞歸就能輕鬆做到，只要注意遞歸函數的結束條件即可。

<code>/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }

    return appendData(head)
} 


func appendData(head *ListNode) []int {
    if head.Next != nil{
        list := appendData(head.Next)
        list = append(list, head.Val)
        return list
    }

    return []int{head.Val}
}/<code>

自然而然，效率不會很高~

反思了一下，其實遞歸還可以再簡短一點

<code>/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return []int{}
    }

    return append(reversePrint(head.Next), head.Val)
}/<code>

結果如下：

題解2：反轉鏈表

想了一下，這樣不行啊，耗時這麼長，試試不用遞歸吧~

然後就想，如果我反轉鏈表呢，再生成數組返回，這樣也可以實現吧？

<code>/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }

    var newHead *ListNode
    res := []int{}
    for head != nil {
        node := head.Next
        head.Next = newHead
        newHead = head
        head = node
    }

    for newHead != nil {
        res = append(res, newHead.Val)
        newHead = newHead.Next
    }

    return res 

}/<code>

結果如下：

解法3：反轉數組

反轉鏈表再獲取數值，可以是可以，會不會有點多餘？還不如直接順序獲取值放到數組，再反轉結果呢~

<code>/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }

    res := []int{}
    for head != nil {
        res = append(res, head.Val)
        head = head.Next
    }

    for i, j := 0, len(res)-1; i < j; {
        res[i], res[j] = res[j], res[i]
        i++
        j--
    }

    return res
}/<code>

至此，結果有了很大的提升：

解法4：棧

這個反轉數組還是感覺好奇怪，有沒有更好的方法呢？把先讀到的放最後，最後的在最前面，棧不就是這樣的數據結構嗎？

<code>/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
import "container/list"

func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }

    res := list.New()
    for head != nil {
        res.PushFront(head.Val)
        head = head.Next
    }

    ret := []int{}
    for e := res.Front(); e != nil; e = e.Next() {
        ret = append(ret, e.Value.(int))
    }

    return ret
}/<code>

三下五除二，搞定！來看看成果：

解法5：遍歷兩次

其實到棧，我以為這題就這樣了，然而......

<code>/** 

 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reversePrint(head *ListNode) []int {
    if head == nil {
        return nil
    }

    count := 0
    newHead := head
    for head != nil {
        count++
        head = head.Next
    }

    res := make([]int, count)
    i := 0
    for newHead != nil {
        res[count-i-1] = newHead.Val
        i++
        newHead = newHead.Next 
    }

    return res
}/<code>

臥槽！！！質的提升，既省去自動擴容的性能，也能提高處理速度：

歡迎關注公眾號：若魚治水，文章會首發在公眾號，也可備註加我備註進群進技術交流群~

閱讀更多 若魚治水 的文章

關鍵字: 鏈表 面試 到頭