关于leetcode个人解题总结:golangleetcode初级删除链表的倒数第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）著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。

双指针是一种很酷很弱小也很常见的解题工具

复杂度剖析

工夫复杂度：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 层。


运行效率失去了显著晋升