反转一个单链表

本贴最后更新于 1842 天前,其中的信息可能已经事过景迁

反转一个单链表。

场景

中文描述

反转一个单链表。

English

Reverse a singly linked list.

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

代码示例

单链表节点

type ListNode struct {
	next  *ListNode
	value interface{}
}

单链表

type LinkedList struct {
	head *ListNode
}

单链表反转
时间复杂度O(n)

func (this *LinkedList) Reverse() {
	//判断链表的长度是否有两个节点 没有两个节点就不用反转了
	if nil == this.head || nil == this.head.next || nil == this.head.next.next {
		return
	}
	var pre *ListNode = nil
	cur := this.head.next
	for cur != nil {
		temp := cur.next
		cur.next = pre
		pre = cur
		cur = temp
	}
	this.head.next = pre
}

打印链表

func (this *LinkedList) Print() {
	cur := this.head.next
	format := ""
	for nil != cur {
		format += fmt.Sprintf("%v", cur.value)
		cur = cur.next
		if nil != cur {
			format += "<-"
		}
	}
	fmt.Println(format)
}

测试代码

var l *LinkedList

// 测试 初始化数据
func init() {
	n5 := &ListNode{value: 5}
	n4 := &ListNode{value: 4, next: n5}
	n3 := &ListNode{value: 3, next: n4}
	n2 := &ListNode{value: 2, next: n3}
	n1 := &ListNode{value: 1, next: n2}
	l = &LinkedList{head: &ListNode{next: n1}}
}

// go test -v -run TestLinkedList_Reverse -o linkedListAlgo_test.go
func TestLinkedList_Reverse(t *testing.T) {
	l.Print()
	l.Reverse()
	l.Print()
}

输出结果

=== RUN   TestLinkedList_Reverse
1<-2<-3<-4<-5
5<-4<-3<-2<-1
--- PASS: TestLinkedList_Reverse (0.00s)
PASS

源码

  • golang

    Go 语言是 Google 推出的一种全新的编程语言,可以在不损失应用程序性能的情况下降低代码的复杂性。谷歌首席软件工程师罗布派克(Rob Pike)说:我们之所以开发 Go,是因为过去 10 多年间软件开发的难度令人沮丧。Go 是谷歌 2009 发布的第二款编程语言。

    497 引用 • 1387 回帖 • 283 关注
  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...