連結清單03--反轉連結清單

連結清單03--反轉連結清單-jz15

• ​​題目概述​​
• ​​解析&參考答案​​
• ​​注意事項​​
• ​​說明​​

題目概述

• 算法說明

  輸入一個連結清單，反轉連結清單後，輸出新連結清單的表頭。

• 測試用例

  輸入：

  {1,2,3}

  輸出：

  {3,2,1}

解析&參考答案

• 解析

  方法1： 使用雙向指針的原理，分别記錄目前已經逆反的連結清單、目前節點、目前節點的下一個節點，每向右移動一次逆反連結清單就增加一個節點；

  方法2： 使用遞歸的原理，每次遞歸都将目前節點的下一個節點的next 指向目前節點，遞歸的結束條件為node為nil 或node.Next 為nil。

• 參考答案

vim jz15.go
package main

import (
    "fmt"
)

type ListNode struct {
    Val  int
    Next *ListNode
}

func CreateList(array []int) *ListNode {
    if len(array) == 0 {
        return nil
    }
    head := &ListNode{array[0], nil}
    p := head
    for i, val := range array {
        if i == 0 {
        } else {
            item := &ListNode{val, nil}
            p.Next = item
            p = p.Next
        }
    }
    return head
}

func ReverseList(pHead *ListNode) *ListNode {
    if pHead == nil || pHead.Next == nil {
        return pHead
    }
    var pPre *ListNode = nil
    pCurrent := pHead
    pNext := pHead.Next
    for pNext != nil {
        pCurrent.Next = pPre
        pPre = pCurrent
        pCurrent = pNext
        pNext = pNext.Next
    }
    pCurrent.Next = pPre
    return pCurrent
}

func ReverseListV2(pHead *ListNode) *ListNode {
    // 遞歸思路： 每次遞歸都将目前節點的下一個節點的next 指向目前節點
    if pHead == nil || pHead.Next == nil {
        return pHead
    }
    pre := ReverseListV2(pHead.Next)
    pHead.Next.Next = pHead
    pHead.Next = nil
    return pre
}

func main() {
    array := []int{1, 2, 3, 4, 5}
    head := CreateList(array)
    ret := ReverseListV2(head)
    fmt.Print(ret.Val)
}      

注意事項

1. to add

說明

1. 目前使用 go1.15.8
2. 參考​​牛客網--劍指offer​​ 标題中jzn(n為具體數字)代表牛客網劍指offer系列第n号題目，例如 jz01 代表牛客網劍指offer中01号題目。

• 筆者最近在學習 golang，是以趁機通過資料結構和算法來進一步熟悉下go語言
• 目前算法主要來源于劍指 offer，後續會進一步補充 LeetCode 上重要算法，以及一些經典算法
• 此處答案僅為參考，不一定是最優解，歡迎感興趣的讀者在評論區提供更優解