剑指 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 的节点分需为两步：定位节点、修改引用。

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

1. 特例处理：  当应删除头节点 head 时，直接返回 head.next 即可。
2. 初始化：  pre = head , cur = head.next 。

3. 定位节点：  当 cur 为空 或 cur 节点值等于 val 时跳出。

   1. 保存当前节点索引，即 pre = cur 。
   2. 遍历下一节点，即 cur = cur.next 。
4. 删除节点：  若 cur 指向某节点，则执行 pre.next = cur.next ；若 cur 指向 null ，代表链表中不包含值为 val 的节点。
5. 返回值：  返回链表头部节点 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;
    }
}

方法二：双指针

思路

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

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

我们首先将 $\textit{slow}$ 指向链表的头节点，同时 $\textit{slow}$ 与 $\textit{fast}$ 同步向后走，当 $\textit{fast}$ 指针指向链表的尾部空节点时，则此时返回 $\textit{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;
    }
}

后记

📝 上篇精讲： 【算法题解】 Day25 动态规划
💖 我是  𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解