以下完整的代码,及测试代码均可从这里获取github
常见的链表操作
单链表反转
方法一:就地反转法
思路
就地反转法,找一个空的节点来充当新的头结点(类似哨兵),然后遍历链表中每一个结点,将每一次遍历到的结点都插入到新的头结点后边,过程如下:
核心代码
- prev指针指向下一次需要反转的节点
- pcur指向待反转的节点
- 将待反转节点插入到newHead后边
prev.Next = pcur.Next
pcur.Next = newHead.Next
newHead.Next = pcur
pcur = prev.Next
完整实现
func (list *List) ReverseList() {
if list.headNode == nil {
fmt.Println("链表为空")
return
}
newHead := &Node{}
newHead.Next = list.headNode
prevNode := newHead.Next
currentNode := prevNode.Next
for currentNode != nil {
prevNode.Next = currentNode.Next
currentNode.Next = newHead.Next
newHead.Next = currentNode
currentNode = prevNode.Next
}
list.headNode = newHead.Next
}
方法二:头插法
思路
这种方法比较简单,就是创建一个新的链表,将待反转的链表的每一个节点,通过头插法的方式,插入到新的链表中(关于单向链表、双向链表、循环链表、双向循环链表的操作,可以看我的上一篇文章)
核心代码
- pcur指向当前要插入的节点
- pnext指向下一个要插入的节点
- newHead为新链表的头结点
1 pnext = pcur.next
2 pcur.Next = newHead.Next
3 newHead.Next = pcur
4 pcur = pnext
完整实现
func (list *List) ReverseListHead() {
if list.headNode == nil {
fmt.Println("链表为空")
return
}
newList := &List{}
currentNode := list.headNode
nextNode := currentNode.Next
for currentNode!=nil {
if newList.headNode == nil {
newList.headNode = currentNode
newList.headNode.Next = nil
currentNode = nextNode
continue
}
nextNode = currentNode.Next
currentNode.Next = newList.headNode
newList.headNode = currentNode
currentNode = nextNode
}
fmt.Println("反转后")
newList.Traverse()
}
循环链表中环的检测
思路
最简单的方式,通过快慢指针的方式处理。有两个指针lowPtr和fastPtr,它们同时从头结点开始遍历链表中的所有结点。lowPtr为慢指针,一次遍历一个结点;fastPtr为快指针,一次遍历两个结点
如果链表中没有环,则fastPtr和lowPtr会先后遍历完所有的结点
如果链表中有环,则快慢指针会先后进入到环中,并且一定会在某一个结点相遇。如果相遇,则该链表中是有环的
代码实现
func (list List) CheckRing() bool {
if list.headNode == nil {
fmt.Println("链表为空")
return false
}
low := list.headNode
fast := list.headNode
for fast.Next != nil {
low = low.Next
fast = fast.Next.Next
//为了防止for中fast.Next出现nil取Next,这里先做个判断
if fast == nil {
return false
}
if low == fast {
return true
}
}
return false
}
用单向循环链表解决:约瑟夫问题
什么是约瑟夫问题
假设有n个人围成一圈,然后对每个人按顺序编号1,2,3,…,n,规定从1号按顺序开始报数,报到k的人出局,之后下一个人再从1开始报数,报到k的人在出局,一直进行下去,问:最后一个出局者为几号?
思路
解法有很多,但是最简单的方式,还是通过单向循环链表来解决。约瑟夫问题首先是一个环,环形链表恰好就非常适合来处理环形问题,将n个人看做环形链表中的每一个结点,当报到k之后便将该结点(人)从循环链表中删除,然后接着从下一个结点继续报数,直到链表为空
代码实现
func (list *List) DealJosephCircle(number int) []interface{} {
var data []interface{}
index := 1
currentNode := list.headNode
preNode := list.headNode
for preNode.Next != list.headNode {
preNode = preNode.Next //刚开始,使preNode指向最后一个节点
}
for currentNode.Next != currentNode {
if index == number {
//删除结点,其实不用考虑是不是头结点或尾结点
data = append(data, currentNode.Data)
preNode.Next = currentNode.Next
currentNode = preNode.Next
index = 1
continue
} else {
index++
}
preNode = currentNode
currentNode = currentNode.Next
}
data = append(data, currentNode.Data)
currentNode = nil
return data
}
有疑问加站长微信联系(非本文作者)