剑指offer31天 第 11 天 双指针（简单）

Day11.1 剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

嗯？ 这不就是删除链表的指定元素。。。 双指针干啥

直接写代码：写的好丑 但是过了
时间：N
空间：1

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val == val:
            return head.next
        point_ = head
        pre = head
        while pre:
            if pre.next != None:
                cur = pre.next  
            else:
                break
            if cur.val == val:
                pre.next = cur.next
            pre = cur
        return point_

执行用时：36 ms, 在所有 Python3 提交中击败了73.67%的用户
内存消耗：15.3 MB, 在所有 Python3 提交中击败了95.08%的用户

这么一看 pre 和 cur 算是双指针吗 — 是的话就算是双指针的题目了

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val == val:
            return head.next

        point_,pre= head,head
        while pre.next:
            cur = pre.next  
            if cur.val == val:
                pre.next = cur.next
            pre = cur

        return point_

代码冗余量搞一下 感觉这个时间空间没法提升了就这把

其实point_ 也没有必要 直接返回head就行

Day11.2 剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

eg:
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

反转链表后再顺序输出？ — 不行 输出的结构就反了

方案1：2次遍历

遍历完长度再输出？ — 时间 2n 空间 1

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        tot_len = 1
        head_ = head
        while head.next:
            tot_len +=1
            head = head.next

        postion = tot_len - k
        while postion:
            head_ = head_.next
            postion -=1

        return head_

执行用时：36 ms, 在所有 Python3 提交中击败了46.87%的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了31.78%的用户

能work 但是效果不太好
时间上不太好 ： 2N
空间害行：1

优化：快慢指针 k个间隔

设置两个指针

• 一个快指针k+n去遍历整个链表
• 一个慢指针n，在离快指针k 个单位距离的地方
• 当快指针到达尾部时，慢指针对应的就是目标值

思路 理清 代码就很简单了

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        slow,fast = head,head
        count = 1 
        while fast:
            if count > k:
                slow = slow.next

            fast = fast.next
            count +=1

        return slow

时间进一步降低