go - 如何在链表的给定索引处插入节点

Question

我正在用Go实现链接列表数据结构。

该方法应按给定索引插入节点。

但是，仅当索引号为0时，此方法才能正常工作。

我一直在阅读和绘图以找出错误，但找不到。

如果有人可以提供见解或解决此错误的方法，我将不胜感激。

您的“insertAt()”逻辑是什么样的？

如果给定的索引无效，则打印错误消息，并完成执行 [按预期工作]

如果给定索引为0，则将该节点作为链接列表的头节点推送 [按预期工作]

将一个新节点插入到链表中的给定索引号中。 [无法正常工作]

以下是(3)的逻辑，该逻辑无法正常工作。

->如果给定的索引有效且大于0，
->迭代链表，直到迭代达到索引(给定索引-1)
->将新节点指向给定索引中的节点，
->使上一个节点指向新节点。

func main() {
    fmt.Println("Hello, world.")

    ll := &LinkedList{
        head:   nil,
        tail:   nil,
        length: 1,
    }

    ll.push(11)
    ll.push(12)
    ll.insertAt(1, 50)

    var testNode = ll.head
    for testNode != nil {                         // This prints, 
        fmt.Println(testNode)                     // &{12 0xc000010200} &{11 <nil>}
        testNode = testNode.next                  // But it should be
    }                                          // &{12 0xc000010200} &{50 memoryaddress} &{11 <nil>}
}

// Node is an object holding its value and the memory address of next node
type Node struct {
    value int
    next  *Node
}

// LinkedList is a list of Node
type LinkedList struct {
    head   *Node
    tail   *Node
    length int
}

// Insert node at a given index
func (ll *LinkedList) insertAt(index, data int) {
    if index < 0 || index > ll.length {
        fmt.Println("invalid index")
    } else if index == 0 {
        newNode := &Node{
            value: data,
            next:  ll.head,
        }
        ll.head = newNode
        ll.length++
    } else {
        newNode := &Node{
            value: data,
            next:  nil,
        }
        counter := 0
        currentNode := ll.head
        var previousNode Node

        // we want to stop iteration at (index - 1)th position
        for counter < index {
            previousNode := currentNode
            currentNode = previousNode.next
            counter++
        }

        newNode.next = currentNode
        previousNode.next = newNode
        ll.length++
    }
}

Answer 1

在实现中有两个错误:

首先:previousNode必须是var previousNode *Node而不是Node。

第二:您要在for循环中重新声明previousNode。因此，您永远不会真正为上一个节点设置指针。使用previousNode=currentNode，而不是:=