第一题 删除链表的倒数第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 层。
运行效率失去了显著晋升