共计 2429 个字符，预计需要花费 7 分钟才能阅读完成。
第一题 删除链表的倒数第 N 个节点
题目信息
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
解题思路
1. 想要删除第 n 个节点，咱们只须要设一个指针，将其定位到 n 的前一个节点，而后将其 next 指针改为指向 n 的下一个节点便可实现操作。
2. 思考到链表长度可能为 1，无奈定位到前一节点，咱们引入一个新的概念
代码如下
func getLength(head *ListNode) (length int) {
for ; head != nil; head = head.Next {length++}
return
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {length := getLength(head)
dummy := &ListNode{0, head}
cur := dummy
for i := 0; i < length-n; i++ {cur = cur.Next}
cur.Next = cur.Next.Next
return dummy.Next
}复杂度剖析
工夫复杂度：O(L+n)，其中 L 是链表的长度。
空间复杂度：O(1)。
另一种办法 先后指针
func removeNthFromEnd(head *ListNode, n int) *ListNode {dummy := &ListNode{0, head}
first, second := head, dummy
for i := 0; i < n; i++ {first = first.Next}
for ; first != nil; first = first.Next {second = second.Next}
second.Next = second.Next.Next
return dummy.Next
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。双指针是一种很酷很弱小也很常见的解题工具
复杂度剖析
工夫复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(1)。
第二题 反转链表
题目信息
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
解题思路
最简略最暴力的思路当然是
应用两个指针，别离指向链表的头部和尾部，并一起向链表两头挪动，一一替换两者的值
代码
func getLength(head *ListNode) (length int) {
for ; head != nil; head = head.Next {length++}
return
}
func reverseList(head *ListNode) *ListNode {
dummy := head// 指向头节点
length := getLength(head)
tail := dummy // 指向尾节点
for i := 0; i < length-1; i++ {tail = tail.Next}
for i:=0;i<length/2;i++{
dummy.Val,tail.Val=tail.Val,dummy.Val
dummy=dummy.Next
tail = dummy // 指向尾节点
for j := 0; j < length-3-2*i; j++ {tail = tail.Next}
}
return head
}复杂度剖析
工夫复杂度：O（8/3n^2）=O（n^2）每次实现替换都须要从新寻找 tail 的地位，寻找的长度从 n / 2 到 n，n 为链表的长度
空间复杂度：O（1）
优化
显然，因为单链表无奈向前搜寻的起因，咱们在向前定位的时候做了十分多无意义的工作，这样的运行效率并不能使咱们称心。
查看官网解答，优化如下
应用一个辅助节点存储前一个节点，并且抉择批改指针的形式替换节点使替换更加不便
代码如下
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。另外还有一种递归解法，比起迭代而言绝对简单
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {return head}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
起源：力扣（LeetCode）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。复杂度剖析
迭代
工夫复杂度：O(n)，其中 n 是链表的长度。须要遍历链表一次。
空间复杂度：O(1)。
递归
工夫复杂度：O(n)，其中 n 是链表的长度。须要对链表的每个节点进行反转操作。
空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度次要取决于递归调用的栈空间，最多为 n 层。
运行效率失去了显著晋升