部分リンクリストの逆引き golang-Golang-php.cn

部分リンクリストの逆引き golang

WBOY

リリース： 2023-05-11 11:34:07

オリジナル

439 人が閲覧しました

リンクリストの反転は古典的な問題であり、広く使用されており、時間の複雑さはそれほど高くなく、実装も難しくありません。この記事では、golang で部分リンクリストを反転するアルゴリズムを実装する方法を紹介します。

リンクリストを反転する

まず、リンクリストを反転する方法を見てみましょう。これは、反復または再帰の 2 つの方法で実装できます。

反復メソッド

3 つのポインタ pre、cur、next を使用して反転操作を反復的に実行します。pre と next は cur の先行者と後続者を保存するためのものです。 . ノードにより、反転後に簡単に再接続できます。コードは次のとおりです。

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

ログイン後にコピー

再帰的メソッド

再帰的メソッドは反復メソッドほど理解するのが簡単ではありませんが、実際には練習の良い例です。再帰的思考。再帰操作で注意する必要があるのは、リンクリストの最後まで再帰した後、末尾ノードを先頭の Next ノードに代入し、末尾ノードを新しい先頭として返す必要があることです。コードは次のとおりです。

func reverseListRecursive(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseListRecursive(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

ログイン後にコピー

部分リンクリストを反転する

リンクリストを反転する基礎を踏まえて、部分リンクリストを反転する方法を見てみましょう。問題の説明は次のとおりです。

リンクリストと 2 つの整数 m および n が与えられた場合、リンクリストを位置 m から n に反転します。アルゴリズムの実装を行う必要があります。

質問を観察することで、検討のために質問を 3 つの部分に分割できます。

m の前: リンクリスト
m を反転する必要はありません。 n 間: リンクリストを反転する必要があります
n 後: リンクリストを反転する必要はありません

したがって、pre 変数と tail 変数を使用して、末尾ノードを記録する必要があります。前半部分と後半部分の先頭ノードを接続し、後半部分を反転してから、前半部分の末尾ノードと後半部分の先頭ノードを接続します。

コードは次のとおりです:

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    if head == nil || m <= 0 || n < m {
        return head
    }
    
    // 特判，如果m=1，则不需要第一部分
    if m == 1 {
        return reverseN(head, n)
    }
    
    //  遍历到m-1位置，记录pre和tail
    var pre *ListNode = nil
    cur := head
    for i := 1; i < m; i++ {
        pre = cur
        cur = cur.Next
    }

    tail := cur // tail 记录第一部分的末尾是 cur             
    // 将第二部分进行反转操作
    new_head := reverseN(cur, n - m + 1)

    // 将第一部分与第二部分重新连接
    tail.Next = new_head
    if pre != nil {
        pre.Next = tail
        return head
    } else {
        return tail
    }
}

// 反转前n个节点
func reverseN(head *ListNode, n int) *ListNode {
    if head == nil || n <= 0 {
        return head
    }
    if n == 1 {
        return head
    }
    var pre *ListNode = nil
    cur := head
    for i := 1; i <= n && cur != nil; i++ {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    head.Next = cur
    return pre
}

ログイン後にコピー

概要

逆リンクリストは、リンクリストの面接の質問に頻繁にアクセスされます。このアルゴリズムのアイデアをマスターすると、次の問題が解決されるだけではありません。逆リンクリストだけでなく、変換操作を他のリンクリストにも拡張します。インタビューを行う際、逆リンクリストは他の質問の例として使用されることがありますが、これはアイデアを発展させる上で非常に重要です。 golangで逆リンクリストや部分リンクリストのアルゴリズムを実装するには、ポインタの使い方やNil判定などに注意する必要がありますが、コードをマスターすれば非常に簡単に実装できます。

以上が部分リンクリストの逆引き golangの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。