算法导论习题:10.2-7 in Go语言

10.2-7题:给出一个时间复杂度为O(n)的非递归过程,实现对一个含n个元素的单链表的逆转。

程序的主要思想就是,转变指标的指向,例如原本是1->2->3->4,现在变成1<-2<-3<-4,就实现了逆转

package main
import (
	"fmt"
)
type Node struct {
 next *Node
 data int
}
type List struct {
 first *Node
}
func (l *List) Insert(d int) {
 node := &Node{nil, d}
 node.next = l.first
 l.first = node 
}
func revise(l *List) {
 if l.first == nil {
 return
 }
 curr := l.first
 next := curr.next
 curr.next = nil 
 for { 
 last := curr
 curr = next 
 next = curr.next
 curr.next = last 
 if next == nil {
 l.first = curr
 break
 } 
 } 
}
func printList(l *List) {
 if l.first == nil {
 fmt.Println("the list is empty")
 return
 }
 fmt.Print("list: ")
 for node := l.first; node != nil; {
 fmt.Printf("[%d]", node.data) 
 node = node.next
 }
 fmt.Print("\n")
}
func main() {
 list := &List{nil}
 for i := 0; i < 10; i++ {
 list.Insert(i)
 }
 printList(list)
 revise(list)
 printList(list) 
}

本文来自:CSDN博客

感谢作者:u013564276

查看原文:算法导论习题:10.2-7 in Go语言

• 编辑
• 预览