【golang】leetcode初级-删除链表的倒数第N个节点&反转链表
第一题 删除链表的倒数第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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。双指针是一种很酷很强大也很常见的解题工具
【【golang】leetcode初级-删除链表的倒数第N个节点&反转链表】复杂度分析
时间复杂度：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复杂度分析
时间复杂度：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 层。
文章图片
文章图片
运行效率得到了显著提升
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长