反转一个单链表。
场景
中文描述
反转一个单链表。
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
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于