# 链表

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/01_listList/level_1/linkList.go

# 基本结构

	type LinkList struct {
	Val interface{}
	Next *LinkList
	}

	// 打印链表
	func (linkList *LinkList) PrintList() {
	if linkList == nil {
	return
	}
	fmt.Println(linkList.Val)
	linkList.Next.PrintList()
	}

	// 新建链表
	func InitLinkList(val interface{}) *LinkList {
	return &LinkList{
	val, nil,
	}
	}

	func insertNode(node, newNode LinkList, postion int) LinkList {
	if postion < 0 {
	panic("error postion")
	}

	// 判断是不是节点
	if newNode.Next != nil {
	panic("newNode is a NodeList")
	}

	// 新建
	if node == nil {
	return newNode
	}

	// 头插
	if postion == 0 {
	newNode.Next = node
	node = newNode
	return node
	}

	head := node
	prev := node
	curr := node.Next

	for postion >= 0 {
	if postion == 1 {
	prev.Next = newNode
	newNode.Next = curr
	break
	}

	if curr == nil {
	panic("error out of length")
	}

	prev = curr
	curr = curr.Next
	postion--
	}

	return head
	}

	func delNode(node LinkList, postion int) LinkList {
	if postion < 0 {
	panic("error postion")
	}

	if node == nil {
	return node
	}

	// 头删
	if postion == 0 {
	return node.Next
	}

	prev := node
	curr := node.Next

	for postion >= 0 {
	if curr == nil {
	panic("error out of length")
	}
	if postion == 1 {
	prev.Next = curr.Next
	break
	}

	prev = curr
	curr = curr.Next
	postion--
	}

	return node
	}

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/01_listList/level_2/topic_1.go

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据保证整个链式结构中不存在环。
解法：求出两个链表的差 A，长的链表先走 A 步，之后两个链表一起走，相同的点就是相遇

	func findFirstCommonNode(headA, headB LinkNode) LinkNode {
	lenA, lenB := 0, 0

	nodeA, nodeB := headA, headB
	for nodeA != nil {
	nodeA = nodeA.Next
	lenA++
	}

	for nodeB != nil {
	nodeB = nodeB.Next
	lenB++
	}

	if lenA > lenB {
	for i := 0; i < lenA-lenB; i++ {
	headA = headA.Next
	}

	} else {
	for i := 0; i < lenB-lenA; i++ {
	headB = headB.Next
	}
	}

	for headA != headB {
	headA = headA.Next
	headB = headB.Next
	}
	return headA
	}

	func TestFindFirstCommonNode(t *testing.T) {
	headA := InitLinkNode(1)
	node2 := InitLinkNode(2)
	node3 := InitLinkNode(3)
	node4 := InitLinkNode(4)

	node3.Next = node4
	node2.Next = node3
	headA.Next = node2

	headA.PrintList()
	fmt.Println()

	headB := InitLinkNode(0)
	node5 := InitLinkNode(5)

	node5.Next = node3
	headB.Next = node5
	headB.PrintList()
	fmt.Println()

	firstCommonNode := findFirstCommonNode(headA, headB)
	fmt.Println(firstCommonNode, node3)
	}

https://leetcode.cn/problems/palindrome-linked-list/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/01_listList/level_2/topic_2.go

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
解法：快慢指针，快的走两步，慢的走一步，快指针到头之后，慢指针所在地即为链表中点。翻转后续链表，遍历翻转链表和初始链表是否一致，如果一致，则是回文。

	func isPalindrome(head *LinkNode) bool {
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
	fast = fast.Next.Next
	slow = slow.Next
	}

	half := slow.Next
	var reverseNode, curr, next *LinkNode
	curr = half
	for curr != nil {
	next = curr.Next
	curr.Next = reverseNode
	reverseNode = curr
	curr = next
	}

	for reverseNode != nil {
	if reverseNode.Val != head.Val {
	return false
	}
	reverseNode = reverseNode.Next
	head = head.Next
	}

	return true
	}

	func TestIsPalindrome(t *testing.T) {
	headA := InitLinkNodeByList([]int{1, 2, 2, 1})
	headA.PrintList()
	fmt.Println(isPalindrome(headA))
	}

https://leetcode.cn/problems/merge-two-sorted-lists/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/01_listList/level_2/topic_3.go

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

	func mergeTwoLists(list1, list2 LinkNode) LinkNode {
	if list1 == nil {
	return list2
	}

	if list2 == nil {
	return list1
	}

	tail := &LinkNode{0, nil}
	head := tail

	for list1 != nil && list2 != nil {
	if list1.Val < list2.Val {
	tail.Next = list1
	tail = tail.Next
	list1 = list1.Next
	continue
	}
	tail.Next = list2
	tail = tail.Next
	list2 = list2.Next
	}

	if list1 != nil {
	tail.Next = list1
	} else {
	tail.Next = list2
	}

	return head.Next
	}

	func TestMergeTwoLists(t *testing.T) {
	headA := InitLinkNodeByList([]int{2, 4, 6})
	headB := InitLinkNodeByList([]int{1, 3, 4})

	headC := mergeTwoLists(headA, headB)
	headC.PrintList()
	}

https://leetcode.cn/problems/remove-linked-list-elements/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/01_listList/level_2/topic_5.go

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
解法：虚拟头指针

	func removeElements(head LinkNode, val int) LinkNode {
	if head == nil {
	return head
	}

	for head != nil && head.Val == val {
	head = head.Next
	}

	tail := head
	pre := &LinkNode{}
	pre.Next = tail
	for tail != nil {
	if tail.Val == val {
	pre.Next = tail.Next
	tail = pre
	}

	pre = tail
	tail = tail.Next
	}

	return head
	}