P02 单链表反转(递归)-蒲公英云

P02 单链表反转(递归)

小咪咪 2022-10-09 02:56 309阅读 0赞

在这里插入图片描述

func RecursionChain(curr *Node) *Node { 
    // curr若本来是nil直接返回
    // curr.next为空则当前节点最最后节点
    if curr == nil || curr.Next == nil { 
        return curr
    }
    // 会无限调用自己，并返回最后一个last值, 将这个last逐层返回即可
    last := RecursionChain(curr.Next)
    // 取到最后节点才开始两两调转指向
    next := curr.Next // 取next
    next.Next = curr  // 将next调转
    curr.Next = nil   // 将curr执行nil，避免双向链表
    return last
}

结果输出

&{1 0xc0001021f0}->&{2 0xc000102200}->&{3 0xc000102210}->&{4 }->
&{4 0xc000102200}->&{3 0xc0001021f0}->&{2 0xc0001021e0}->&{1 }->

测试

package main
import "fmt"
type Node struct { 
    ID   int8
    Next *Node
}
func ShowListNode(head *Node) { 
    for curr := head; curr != nil; curr = curr.Next { 
        fmt.Print(curr, "->")
    }
    fmt.Println()
}
func BuildListNodeByList(list []int8) *Node { 
    head := &Node{ }
    curr := head
    for _, id := range list { 
        temp := &Node{ ID: id}
        curr.Next = temp
        curr = temp
    }
    return head.Next
}
func main() { 
    head := BuildListNodeByList([]int8{ 1, 2, 3, 4})
    ShowListNode(head)
    head3 := RecursionChain(head)
    ShowListNode(head3)
}