带头链表的实现

package linkedList

import "fmt"

/**
go实现带头单链表基本操作
*/

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

type LinkedList struct {
	head   *ListNode
	length uint32
}

func NewListNode(v interface{}) *ListNode {
	return &ListNode{value: v, next: nil}
}

func (node *ListNode) GetNext() *ListNode {
	return node.next
}

func (node *ListNode) SetNext(next *ListNode) {
	node.next = next
}

func (node *ListNode) GetValue() interface{} {
	return node.value
}

func NewLinkedList() *LinkedList {
	return &LinkedList{NewListNode(0), 0}
}

// InsertAfter 在某个节点后面插入节点
func (list *LinkedList) InsertAfter(p *ListNode, v interface{}) bool {
	if p == nil || v == nil {
		return false
	}
	newNext := NewListNode(v)
	oldNext := p.next
	p.next = newNext
	newNext.next = oldNext
	list.length++
	return true
}

// InsertBefore 在某个节点前面插入节点
func (list *LinkedList) InsertBefore(p *ListNode, v interface{}) bool {
	if p == nil || p == list.head || v == nil {
		return false
	}
	pre := list.head
	cur := list.head.next
	for cur != nil {
		if cur == p {
			break
		}
		pre = cur
		cur = cur.next
	}
	if cur == nil {
		return false
	}
	newNode := NewListNode(v)
	pre.next = newNode
	newNode.next = cur
	list.length++
	return true
}

// InsertToHead 在链表头部插入节点
func (list *LinkedList) InsertToHead(v interface{}) bool {
	return list.InsertAfter(list.head, v)
}

// InsertToTail 在链表尾部插入节点
func (list *LinkedList) InsertToTail(v interface{}) bool {
	if v == nil {
		return false
	}
	cur := list.head
	for cur.next != nil {
		cur = cur.next
	}
	return list.InsertAfter(cur, v)
}

// FindByIndex 通过索引查找节点
func (list *LinkedList) FindByIndex(index uint32) *ListNode {
	if index >= list.length {
		return nil
	}
	cur := list.head.next
	i := uint32(0)
	for ; i < index; i++ {
		cur = cur.next
	}
	return cur
}

// DeleteNode 删除传入的节点
func (list *LinkedList) DeleteNode(p *ListNode) bool {
	if p == nil {
		return false
	}
	pre := list.head
	cur := list.head.next
	for cur != nil {
		if cur == p {
			break
		}
		pre = cur
		cur = cur.next
	}
	if cur == nil {
		return false
	}
	pre.next = cur.next
	cur = nil
	list.length--
	return true
}

// Print 打印链表
func (list *LinkedList) Print() {
	cur := list.head.next
	for cur != nil {
		fmt.Printf("%v->", cur.GetValue())
		cur = cur.next
	}
	fmt.Println()
}

链表翻转

新建一个链表，在遍历当前链表的同时用这个新链表来反向记录（往头部新增结点）

// Reverse 链表翻转
func (list *LinkedList) Reverse() {
	newList := NewLinkedList()
	cur := list.head.next
	for cur != nil {
		newList.InsertToHead(cur.GetValue())
		cur = cur.next
	}
	list.head.next = newList.head.next
}

删除链表倒数第n个结点

思路：
假设有n个结点，现在要删除倒数第2个结点，即n-1；
我们可以声明快慢指针指向第一个结点，快指针先走2步到第3个结点的位置；
此后快慢结点同时走，每次走一步，慢指针始终落后于快指针2个结点；
那么当快指针走到第n个结点的时候，慢指针处于第n-2个结点，即n-1个结点的前一个结点，此时可以用(n-2).next=(n-2).next.next来删除第n-1个结点。

// DeleteLastN 删除倒数第n个结点
func (list *LinkedList) DeleteLastN(n uint32) bool {
	if list.head.next == nil || list.length < n {
		return false
	}
	slow := list.head.next
	fast := list.head.next
	i := uint32(0)
	for ; i < n; i++ {
		fast = fast.next
	}
	if fast == nil {
		list.head.next = list.head.next.next
		return true
	}
	for fast.next != nil {
		fast = fast.next
		slow = slow.next
	}

	slow.next = slow.next.next
	return true
}

找到链表的中间结点

快慢指针2分法

// FindMiddleNode 找到链表的中间结点
func (list *LinkedList) FindMiddleNode() *ListNode {
	if list.head.next == nil {
		return nil
	}
	slow := list.head.next
	fast := list.head.next
	for fast.next != nil && fast.next.next != nil {
		fast = fast.next.next
		slow = slow.next
	}

	return slow
}

链表环

检测链表是否有环

// HasCircle 链表是否有环
func (list *LinkedList) HasCircle() bool {
	if list.head.next == nil {
		return false
	}
	slow := list.head.next
	fast := list.head.next.next
	for fast != nil && fast.next != nil {
		if slow == fast {
			return true
		}
		slow = slow.next
		fast = fast.next.next
	}
	return false
}

寻找环的入口

乌龟每次移动一步，兔子每次移动两部，那么当龟兔第一次相遇的时候，兔子经过的节点数就是乌龟的两倍，假设这时乌龟已经在环上跑了p圈, 兔子已经在环上跑了q圈，那么就有如下等式：


我们把乌龟放回起点，兔子保持在第一次相遇点不动，同时每次前进一步，当乌龟来到环的入口的时候（经历了m个结点），兔子在环上走了(q-2p)圈-k个结点，从上图可以看出，q-2p圈会让兔子保持在原点，再减去k个结点，则刚好是环的入口，这时龟兔会相遇。

// CircleStart 如果链表有环，找到环的开始位置
func (list *LinkedList) CircleStart() *ListNode {
	// 链表无环，直接返回nil
	if !list.HasCircle() {
		return nil
	}

	// 找到快慢指针第一次相遇点
	slow := list.head.next
	fast := list.head.next.next
	for fast != nil && fast.next != nil {
		if slow == fast {
			break
		}
		slow = slow.next
		fast = fast.next.next
	}

	// slow指针指向链表头
	slow = list.head

	// 快慢指针以相同速度前进直到相遇
	for slow != fast {
		slow = slow.next
		fast = fast.next
	}
	return slow
}

参考

原文链接