golangの連結リストを反転する方法

Go言語で連結リストを反転させるには、反復処理または再帰処理の方法を使用できます。

イテレーション方式のコードを以下に示します。

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode // 上一个节点
    curr := head       // 当前遍历的节点

    for curr != nil {
        next := curr.Next // 保存下一个节点
        curr.Next = prev  // 将当前节点的Next指向上一个节点
        prev = curr       // 更新上一个节点为当前节点
        curr = next       // 更新当前节点为下一个节点
    }

    return prev // 返回反转后的头节点
}

再帰的に処理するコードは次のとおりです。

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next) // 先反转后面的链表
    head.Next.Next = head             // 将当前节点的下一个节点的Next指向当前节点，实现反转
    head.Next = nil                   // 将当前节点的Next置为nil，防止形成环
    return newHead                    // 返回新的头节点
}

Go言語でLinkedListを反転するコード。反復と再帰の2つのパターンがある。