【算法题解】 Day26 双指针

sidiot

发布于 2023-08-31 13:55:16

2300

文章被收录于专栏：技术大杂烩技术大杂烩

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

题目

剑指 Offer 18. 删除链表的节点难度：easy

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

返回删除后的链表的头节点。

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同

方法一：双指针

思路

本题删除值为 val 的节点分需为两步：定位节点、修改引用。

定位节点： 遍历链表，直到 head.val == val 时跳出，即可定位目标节点。
修改引用： 设节点 cur 的前驱节点为 pre ，后继节点为 cur.next ；则执行 pre.next = cur.next ，即可实现删除 cur 节点。

特例处理： 当应删除头节点 head 时，直接返回 head.next 即可。
初始化： pre = head , cur = head.next 。
定位节点： 当 cur 为空或 cur 节点值等于 val 时跳出。
1. 保存当前节点索引，即 pre = cur 。
2. 遍历下一节点，即 cur = cur.next 。
删除节点： 若 cur 指向某节点，则执行 pre.next = cur.next ；若 cur 指向 null ，代表链表中不包含值为 val 的节点。
返回值： 返回链表头部节点 head 即可。

解题

Python：

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

Java：

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val) return head.next;
        ListNode pre = head, cur = head.next;
        while(cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if(cur != null) pre.next = cur.next;
        return head;
    }
}

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

题目

剑指 Offer 22. 链表中倒数第k个节点难度：easy

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

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

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

返回链表 4->5.

方法一：顺序查找

思路

最简单直接的方法即为顺序查找，假设当前链表的长度为 n，则我们知道链表的倒数第 k个节点即为正数第 n−k个节点，此时我们只需要顺序遍历到链表的第 n−k 个节点即为倒数第 k个节点。

我们首先求出链表的长度 n，然后顺序遍历到链表的第 n−k 个节点返回即可。

解题

Python：

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

        node = head
        for _ in range(n-k):
            node = node.next
        
        return node

Java：

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int n = 0;
        ListNode node = null;

        for (node = head; node != null; node = node.next) {
            n++;
        }
        for (node = head; n > k; n--) {
            node = node.next;
        }

        return node;
    }
}

方法二：双指针

思路

快慢指针的思想。我们将第一个指针 fast指向链表的第 k+1个节点，第二个指针 slow 指向链表的第一个节点，此时指针 fast 与 slow二者之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针 fast走到链表的尾部空节点时，则此时 slow指针刚好指向链表的倒数第 k 个节点。

我们首先将 fast指向链表的头节点，然后向后走 k 步，则此时 fast指针刚好指向链表的第 k+1 个节点。

我们首先将 slow 指向链表的头节点，同时 slow与 fast同步向后走，当 fast 指针指向链表的尾部空节点时，则此时返回 slow 所指向的节点即可。

解题

Python：

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast, slow = head, head

        while fast and k > 0:
            fast, k = fast.next, k - 1
        while fast:
            fast,slow = fast.next,slow.next
        
        return slow

Java：

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-25，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历