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

u013564276 · · 1941 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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语言

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1941 次点击  
加入收藏 微博
1 回复  |  直到 2000-01-01 00:00:00
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传