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) }
有疑问加站长微信联系(非本文作者)
![](https://static.golangjob.cn/static/img/footer.png?imageView2/2/w/280)