25-附：链表专题汇总.md

```Go
package main

import (
	"fmt"
	"math"
)

// Node 链表的节点结构
type Node struct {
	Value int
	Next *Node
}

// DuLNode 双向链表的节点结构
type DuLNode struct {
	Value int
	Pre *DuLNode
	Next *DuLNode
}

// 1、检测链表是否成环。返回成环是否，第一次相遇并不保证是成环的节点
func hasCycle(head *Node) bool {
	if head == nil || head.Next == nil {
		return false
	}

	slow := head
	fast := head.Next

	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}

		slow = slow.Next
		fast = fast.Next.Next
	}

	// 有环的话一定追的上，但不一定是第一次成环的节点
	return true
}

// 2、传入头节点，翻转单项链表。返回翻转后的新的头节点
func reverseLinkedList(head *Node) *Node {
	var pre *Node
	var next *Node

	for head != nil {
		next = head.Next
		head.Next = pre
		pre = head
		head = next
	}

	return pre
}

// 3、移除链表中等于值的节点。返回处理后的头结点
// 例如：1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。
func removeValue(head *Node, num int) *Node {

	// 从链表的头开始，舍弃掉开头的且连续的等于num的节点
	for head != nil {
		if head.Value != num {
			break
		}
		head = head.Next
	}

	if head == nil { // 头结点处理完毕，发现全部都等于num的情况。
		return head
	}

	// head来到 第一个不需要删的位置
	pre := head
	cur := head

	// 快慢指针
	for cur != nil {
		if cur.Value == num { // 快指针cur向下滑动，如果值等于num，则暂时把下一个节点给慢指针的下一个指向。从而跳过等于num的节点
			pre.Next = cur.Next
		} else { // cur此时到了不等于num的节点，则慢指针追赶上去。达到的效果就是等于num的节点都被删掉了
			pre = cur
		}

		// 快指针向下滑动
		cur = cur.Next
	}
	return head
}

// 4、打印两个有序链表的公共部分
// 例如：head1: 1->2->3->3->4->5 head2: 0->0->1->2->3->3->7->9
// 公共部分为：1 2 3 3
func printCommonPart(head1, head2 *Node) {
	fmt.Println("Common Part: ")

	for head1 != nil && head2 != nil {
		if head1.Value < head2.Value {
			head1 = head1.Next
		} else if head1.Value > head2.Value {
			head2 = head2.Next
		} else {
			fmt.Println(head1.Value)
			head1 = head1.Next
			head2 = head2.Next
		}
	}
	fmt.Println()
}

// 5、删除单链表的倒数第k个节点
func removeLastKthNode(head *Node, lastKth int) *Node {
	if head == nil || lastKth < 1 {
		return head
	}

	// cur指针也指向链表头节点
	cur := head
	// 检查倒数第lastKth个节点的合法性
	for cur != nil {
		lastKth--
		cur = cur.Next
	}

	// 需要删除的是头结点
	if lastKth == 0 {
		head = head.Next
	}

	if lastKth < 0 {
		// cur回到头结点
		cur = head
		for lastKth != 0 {
			lastKth++
			cur = cur.Next
		}

		// 此次cur就是要删除的前一个节点。把原cur.next删除
		cur.Next = cur.Next.Next
	}

	// lastKth > 0的情况，表示倒数第lastKth节点比原链表程度要大，即不存在
	return head
}

// 6、删除链表中间节点
// 思路：如果链表为空或者只有一个节点，不做处理。链表两个节点删除第一个节点，链表三个节点，删除中间第二个节点，链表四个节点，删除上中点
func removeMidNode(head *Node) *Node {
	// 无节点，或者只有一个节点的情况，直接返回
	if head == nil || head.Next == nil {
		return head
	}

	// 链表两个节点，删除第一个节点
	if head.Next.Next == nil {
		// free first node mem
		return head.Next
	}

	pre := head
	cur := head.Next.Next

	// 快慢指针
	if cur.Next != nil && cur.Next.Next != nil {
		pre = pre.Next
		cur = cur.Next.Next
	}

	// 快指针走到尽头，慢指针奇数长度停留在中点，偶数长度停留在上中点。删除该节点
	pre.Next = pre.Next.Next
	return head
}

// 7、给定一个链表，如果成环，返回成环的那个节点
// 思路：
// 1. 快慢指针fast和slow，开始时，fast和slow都指向头节点，fast每次走两步，slow每次走一步
// 2. 快指针向下移动的过程中，如果提前到达null，则链表无环，提前结束
// 3. 如果该链表成环，那么fast和slow一定在环中的某个位置相遇
// 4. 相遇后，立刻让fast回到head头结点，slow不动，fast走两步改为每次走一步。fast和slow共同向下滑动，再次相遇，就是成环节点

func getLoopNode(head *Node) *Node {
	// 节点数目不足以成环，返回不存在成环节点
	if head == nil || head.Next == nil || head.Next.Next == nil {
		return nil
	}

	n1 := head.Next // slow指针
	n2 := head.Next.Next  // fast指针

	for n1 != n2 {
		// 快指针提前到达终点，该链表无环
		if n2.Next == nil || n2.Next.Next == nil {
			return nil
		}

		n2 = n2.Next.Next
		n1 = n1.Next
	}

	// 确定成环，n2回到头节点
	n2 = head

	for n1 != n2 {
		n2 = n2.Next
		n1 = n1.Next
	}

	// 再次相遇节点，就是成环节点
	return n1
}


// 8、判断两个无环链表是否相交，相交则返回相交的第一个节点
// 由于单链表，两个链表相交要不然两个无环链表相交，最后是公共部分；要不然两个链表相交，最后是成环部分.
// 思路：
// 1. 链表1从头结点遍历，统计长度，和最后节点end1
// 2. 链表2从头结点遍历，统计长度，和最后节点end2
// 3. 如果end1不等一end2则一定不相交，如果相等则相交，算长度差，长的链表遍历到长度差的长度位置，两个链表就汇合在该位置
func noLoop(head1, head2 *Node) *Node {
	if head1 == nil || head2 == nil {
		return nil
	}

	cur1 := head1
	cur2 := head2
	n := 0

	for cur1.Next != nil {
		n++
		cur1 = cur1.Next
	}

	for cur2.Next != nil {
		n--
		cur2 = cur2.Next
	}

	// 最终没汇聚，说明两个链表不相交
	if cur1 != cur2 {
		return nil
	}

	if n <= 0 {
		cur1 = cur2
	}

	if cur1 == head1 {
		cur2 = head2
	} else {
		cur2 = head1
	}

	n = int(math.Abs(float64(n)))

	for n != 0 {
		n--
		cur1 = cur1.Next
	}

	for cur1 != cur2 {
		cur1 = cur1.Next
		cur2 = cur2.Next
	}

	return cur1
}

// 9、合并两个有序链表
func mergeTwoList(head1, head2 *Node) *Node {
	// base case
	if head1 == nil {
		return head2
	}
	if head2 == nil {
		return head1
	}

	var head *Node

	// 选出两个链表较小的头作为整个合并后的头结点
	if head1.Value <= head2.Value {
		head = head1
	} else {
		head = head2
	}

	// 链表1的准备合并的节点，就是头结点的下一个节点
	cur1 := head.Next
	// 链表2的准备合并的节点，就是另一个链表的头结点
	var cur2 *Node
	if head == head1 {
		cur2 = head2
	} else {
		cur2 = head1
	}

	// 最终要返回的头结点，预存为head，使用引用拷贝的pre向下移动
	pre := head
	for cur1 != nil && cur2 != nil {
		if cur1.Value <= cur2.Value {
			pre.Next = cur1
			// 向下滑动
			cur1 = cur1.Next
		} else {
			pre.Next = cur2
			// 向下滑动
			cur2 = cur2.Next
		}

		// pre向下滑动
		pre = pre.Next
	}

	// 有一个链表耗尽了，没耗尽的链表直接拼上
	if cur1 != nil {
		pre.Next = cur1
	} else {
		pre.Next = cur2
	}
	
	return head
}
```