以下完整的代码，及测试代码均可从这里获取github
常见的链表操作
单链表反转
方法一：就地反转法
###### 思路
就地反转法，找一个空的节点来充当新的头结点（类似哨兵），然后遍历链表中每一个结点，将每一次遍历到的结点都插入到新的头结点后边，过程如下：
###### 核心代码
prev 指针指向下一次需要反转的节点
pcur 指向待反转的节点
将待反转节点插入到 newHead 后边
prev.Next = pcur.Nextpcur.Next = newHead.NextnewHead.Next = pcurpcur = 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.next2 pcur.Next = newHead.Next3 newHead.Next = pcur4 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}
复制代码
评论