Golang实现链表反转的方法与技巧

Golang实现链表反转的方法与技巧 我们被分配了反转链表的任务，具体如下：

package main
 
import "fmt"
 
type Node struct {
    prev *Node
    next *Node
    key  interface{}
}
 
type List struct {
    head *Node
    tail *Node
}
 
func (L *List) Insert(key interface{}) {
    list := &Node{
        next: L.head,
        key:  key,
    }
    if L.head != nil {
        L.head.prev = list
    }
    L.head = list
 
    l := L.head
    for l.next != nil {
        l = l.next
    }
    L.tail = l
}
 
func (l *List) Display() {
    list := l.head
    for list != nil {
        fmt.Printf("%+v ", list.key)
        list = list.next
    }
    fmt.Println()
}
 
func Display(list *Node) {
    for list != nil {
        fmt.Printf("%v ", list.key)
        list = list.next
    }
    fmt.Println()
}
 
func ShowBackwards(list *Node) {
    for list != nil {
        fmt.Printf("%v ", list.key)
        list = list.prev
    }
    fmt.Println()
}
 
func (l *List) Reverse() {
    curr := l.head
    var prev *Node
    l.tail = l.head
 
    for curr != nil {
        next := curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    l.head = prev
    Display(l.head)
}
 
func main() {
    link := List{}

    fmt.Printf("Head: %v\n", link.head.key)
    fmt.Printf("Tail: %v\n", link.tail.key)
    link.Display()
    fmt.Printf("head: %v\n", link.head.key)
    fmt.Printf("tail: %v\n", link.tail.key)
    link.Reverse()
}

更多关于Golang实现链表反转的方法与技巧的实战教程也可以访问 https://www.itying.com/category-94-b0.html

5 回复

如何？你能分享一下错误输出吗？

帮助我们帮助你！不是每个人在遇到编译器时都会阅读论坛，他们可能会直接尝试编译你的代码……

更多关于Golang实现链表反转的方法与技巧的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


请告诉我们代码产生了什么问题。

输出结果与您的预期不同吗？是在编译过程中出错了吗？还是其他问题？

嗯，通过手机复制/粘贴也不方便。

如果所有必要的数据都能直接获取，而不需要那些愿意提供帮助的人做额外的工作，那么提供帮助就会容易得多。

而且这甚至会在运行时引发恐慌，而不是编译错误。

问题在我们修改代码后得到解决，修改后的代码如下：

func main() {
        var n int
    _, err := fmt.Scanln(&n)
    if err != nil || n < 0 {
        return
    }
    link := List{}
    s := make([]int, n)
    for i := range s {
        fmt.Scanln(&s[i])
        link.Insert(s[i])
    }
    fmt.Printf("Head: %v\n", link.head.key)
    fmt.Printf("Tail: %v\n", link.tail.key)
    link.Display()
    fmt.Printf("head: %v\n", link.tail.key)
    fmt.Printf("tail: %v\n", link.head.key)
    link.Reverse()
}

以下是针对链表反转问题的专业实现与优化建议。你提供的代码已经实现了反转功能，但存在一些边界条件处理问题，例如空链表情况下的 link.head.key 访问会导致 panic。以下是修正后的完整代码，包含两种常见的反转方法：

方法一：迭代反转（优化版）

func (l *List) Reverse() {
    // 处理空链表或单节点链表
    if l.head == nil || l.head.next == nil {
        return
    }
    
    curr := l.head
    var prev *Node
    l.tail = l.head  // 更新尾节点
    
    for curr != nil {
        next := curr.next  // 临时保存下一个节点
        curr.next = prev   // 反转指针方向
        curr.prev = next   // 更新prev指针（双向链表需要）
        prev = curr        // 前移prev指针
        curr = next        // 前移当前指针
    }
    
    l.head = prev  // 更新头节点
    l.head.prev = nil  // 确保新头节点的prev为nil
}

方法二：递归反转（替代方案）

func (l *List) ReverseRecursive() {
    l.head = reverseHelper(l.head)
    // 更新尾节点
    l.tail = l.head
    for l.tail != nil && l.tail.next != nil {
        l.tail = l.tail.next
    }
}

func reverseHelper(node *Node) *Node {
    if node == nil || node.next == nil {
        return node
    }
    
    newHead := reverseHelper(node.next)
    node.next.next = node
    node.prev = node.next  // 更新prev指针
    node.next = nil
    return newHead
}

修正后的main函数：

func main() {
    link := List{}
    
    // 插入测试数据
    link.Insert(5)
    link.Insert(4)
    link.Insert(3)
    link.Insert(2)
    link.Insert(1)
    
    fmt.Println("原始链表:")
    link.Display()
    
    // 安全访问head和tail
    if link.head != nil {
        fmt.Printf("Head: %v\n", link.head.key)
    }
    if link.tail != nil {
        fmt.Printf("Tail: %v\n", link.tail.key)
    }
    
    // 反转链表
    link.Reverse()
    
    fmt.Println("\n反转后链表:")
    link.Display()
    
    if link.head != nil {
        fmt.Printf("New Head: %v\n", link.head.key)
    }
    if link.tail != nil {
        fmt.Printf("New Tail: %v\n", link.tail.key)
    }
    
    // 测试反向遍历
    fmt.Println("\n反向遍历:")
    ShowBackwards(link.tail)
}

关键技巧说明：

  1. 边界处理：始终检查空链表和单节点链表情况
  2. 指针更新：反转时需要同时处理next和prev指针（双向链表）
  3. 尾节点维护：反转后需要更新List的tail指针
  4. 时间复杂度：迭代法O(n)，递归法O(n)但可能有栈溢出风险
  5. 内存效率：迭代法O(1)，递归法O(n)（调用栈空间）

测试输出示例：

原始链表:
1 2 3 4 5 
Head: 1
Tail: 5

反转后链表:
5 4 3 2 1 
New Head: 5
New Tail: 1

反向遍历:
1 2 3 4 5

这个实现正确处理了双向链表的反转，包括prev指针的更新，并确保了头尾节点的正确维护。

回到顶部