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

u013564276 · · 1924 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

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)    
}

有疑问加站长微信联系（非本文作者）