# 链表翻转

https://github.com/Twelveeee/AlgorithmCamp2023/tree/main/02_reverselist

# 基本结构

# 链表构建

	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 reverseListV1(head LinkNode) LinkNode {

	curr := head
	newList, temp := &LinkNode{}, &LinkNode{}

	for curr != nil {
	temp = curr.Next
	curr.Next = newList.Next
	newList.Next = curr
	curr = temp
	}

	return newList.Next
	}

# 直接操作链表实现反转

	// 直接操作链表实现翻转
	func reverseListV2(head LinkNode) LinkNode {

	curr := head
	temp := &LinkNode{}
	var pre *LinkNode

	for curr != nil {
	temp = curr.Next
	curr.Next = pre
	pre = curr
	curr = temp
	}

	return pre
	}

# 递归翻转

	// 递归
	func reverseListV3(head LinkNode) LinkNode {

	if head.Next == nil \|\| head == nil {
	return head
	}

	newHead := reverseListV3(head.Next)

	// 将当前节点的下一个节点的 Next 指针指向当前节点，实现翻转
	head.Next.Next = head
	head.Next = nil

	return newHead
	}

# 算法题

# 1. 指定区间反转

https://leetcode.cn/problems/reverse-linked-list-ii/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/02_reverselist/level_2/topic_1.go

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
解法：建立虚拟头节点，走 left 步，再对 right-left 步进行翻转，保证 pre 节点一直指向翻转链表的头节点

	func reverseBetween(head ListNode, left int, right int) ListNode {
	left = left - 1
	right = right - 1

	dummyHead := &ListNode{}
	dummyHead.Next = head

	pre := dummyHead
	for i := 0; i < left; i++ {
	pre = pre.Next
	}

	curr := pre.Next
	temp := &ListNode{}
	for i := 0; i < right-left; i++ {
	temp = curr.Next
	curr.Next = temp.Next
	temp.Next = pre.Next
	pre.Next = temp
	}

	return dummyHead.Next
	}

# 2. 两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/02_reverselist/level_2/topic_2.go

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
解法：画个图一下走两步

	func swapPairs(head ListNode) ListNode {
	dummyHead := &ListNode{}
	dummyHead.Next = head

	pre, curr, next := dummyHead, dummyHead.Next, &ListNode{}

	for curr != nil && curr.Next != nil {
	next = curr.Next
	curr.Next = curr.Next.Next
	pre.Next = next
	next.Next = curr

	pre = pre.Next.Next
	curr = pre.Next
	}

	return dummyHead.Next
	}

# 3. 链表加法

https://leetcode.cn/problems/add-two-numbers-ii/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/02_reverselist/level_2/topic_4.go

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
解法：可以用翻转链表，但是用两个栈会快点

	func addTwoNumbers(l1 ListNode, l2 ListNode) *ListNode {
	list1 := make([]int, 0, 100)
	list2 := make([]int, 0, 100)

	for l1 != nil {
	list1 = append(list1, l1.Val)
	l1 = l1.Next
	}

	for l2 != nil {
	list2 = append(list2, l2.Val)
	l2 = l2.Next
	}

	ans := &ListNode{}

	index1, index2 := len(list1)-1, len(list2)-1
	carry := 0
	for index1 >= 0 \|\| index2 >= 0 \|\| carry != 0 {
	temp := 0
	if carry != 0 {
	temp += carry
	carry = 0
	}
	if index1 >= 0 {
	temp += list1[index1]
	index1--
	}
	if index2 >= 0 {
	temp += list2[index2]
	index2--
	}

	if temp >= 10 {
	carry, temp = temp/10, temp%10
	}

	ans.Next = &ListNode{temp, ans.Next}

	}

	return ans.Next
	}

# 4.K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/02_reverselist/level_3/topic_1.go

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
解法：先 check 能不能进行反转，然后进行翻转

	func reverseKGroup(head ListNode, k int) ListNode {
	dummpHead, tempNext := &ListNode{}, &ListNode{}
	dummpHead.Next = head

	pre := dummpHead
	curr := pre.Next
	for curr != nil {
	// check
	tail := curr
	for i := 0; i < k; i++ {
	if tail == nil {
	return dummpHead.Next
	}
	tail = tail.Next
	}

	// do reverse
	for i := 0; i < k-1; i++ {
	tempNext = curr.Next
	curr.Next = tempNext.Next
	tempNext.Next = pre.Next
	pre.Next = tempNext
	}

	pre = curr
	curr = curr.Next

	}

	return dummpHead.Next
	}

数据结构算法