LeetCode75学习计划-链表

算法解题思路很多会借鉴于题解区，如果侵权请联系删除。

本章节知识点为链表。

反转链表

题目标签：

• 链表
• 递归

题目难度： Easy

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

解题思路：

• 遍历链表时，将当前节点的 next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用

代码实现：

type ListNode struct {
  Val int
  Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
  // prev，current，next三个节点流转实现反转
  var prev *ListNode
  current := head
  for current != nil {
    next := current.Next
    current.Next = prev
    prev = current
    current = next
  }
  return prev
}

删除链表的中间节点

题目标签：

• 链表
• 双指针

题目难度： Medium

题目描述：

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 ``n 链表的中间节点是从头数起第 ⌊n / 2⌋个节点（下标从0开始），其中⌊x⌋表示小于或等于x` 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

解题思路：

• 这里用快慢指针的思路即可，快指针遍历完整个链表之后，慢指针指向的节点就是中间节点
• 因为要删除中间节点，所以要有一个额外的前导指针指向慢指针的前一个节点

代码实现：

type ListNode struct {
  Val int
  Next *ListNode
}

func deleteMiddle(head *ListNode) *ListNode {
  if head.Next == nil {
    return nil
  }
  // 指针
  slow := head
  fast := head
  var prev *ListNode
  for fast != nil && fast.Next != nil {
    fast = fast.Next.Next
    prev = slow
    slow = slow.Next
  }
  prev.Next = slow.Next
  return head
}

奇偶链表

题目标签：

• 链表

题目难度： Medium

题目描述：

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

解题思路：

• 可以先把链表按照奇偶数分为两个链表，最后组合起来

代码实现：

func oddEvenList(head *ListNode) *ListNode {
  // 如果头节点不存在直接返回
  if head == nil {
    return head
  }
  // head作为奇数链表的头节点，evenHead作为偶数链表的头节点
  evenHead := head.Next
  // odd和even分别指向奇偶节点
  odd := head
  even := evenHead
  // 循环链表，分离出奇偶链表
  for even != nil && even.Next != nil {
    odd.Next = even.Next
    odd = odd.Next
    even.Next = odd.Next
    even = even.Next
  }
  // 奇数链表的最后拼接上偶数链表
  odd.Next = evenHead
  return head
}

链表最大孪生和

题目标签：

• 链表
• 栈
• 双指针

题目难度： Medium

题目描述：

在一个大小为n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。

• 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

解题思路：

• 采用快慢指针的思路，快指针走完链表之后，慢指针走完了一半的链表，在这个过程中将慢指针走过的值加入到栈中
• 之后慢指针继续向后移动，指向的每一个节点都与栈顶弹出的元素相加，计算该节点的孪生和，最后求的一个最大的孪生和

代码实现：

func pairSum(head *ListNode) int {
  // 快慢指针
  slow := head
  fast := head
  // 栈存储满指针走过的值
  stack := []int{}
  // 当快指针走完链表之后，慢指针走完了一半的链表
  // 在这个过程中将慢指针走过的值加入栈中
  for fast != nil {
    stack = append(stack, slow.Val)
    slow = slow.Next
    fast = fast.Next.Next
  }
  // 此时慢指针可以继续往前走，没走一个就从栈顶弹出一个元素
  // 他们两个就是孪生节点
  maxValue := 0
  for slow != nil {
    maxValue = max(maxValue, slow.Val + stack[len(stack) - 1])
    // 更新慢指针位置
    slow = slow.Next
    // 弹出栈顶元素
    stack = stack[:len(stack)-1]
  }
  return maxValue
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}