数据结构与算法系列之链表操作全集(二)(GO)
source link: https://segmentfault.com/a/1190000037693457
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
以下完整的代码,及测试代码均可从这里获取 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 }
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK