剑指offer一刷：双指针

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

难度：简单

没什么好说的，注意删除的节点为头节点的这一特殊情况即可。

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;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/509cy5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

难度：简单

方法一：统计链表长度

  1. 先遍历统计链表长度，记为 n；
  2. 设置一个指针走 (n-k) 步，即可找到链表倒数第 k 个节点；

方法二：双指针

该方法不需要像上个方法那样统计链表长度。

一前一后两个指针，前指针先走k步，然后双指针同时移动，直到前指针走过尾结点时返回后指针。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head, latter = head;
        for(int i = 0; i < k; i++) {
            if(former == null) return null;
            former = former.next;
        }
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/588dhc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。

剑指 Offer 25. 合并两个排序的链表

难度：简单

引入伪头节点：由于初始状态合并链表中无节点，因此循环第一轮时无法将节点添加到合并链表中。解决方案：初始化一个辅助节点 dum 作为合并链表的伪头节点，将各节点添加至 dum 之后。

算法流程：

  1. 初始化：伪头节点 dum ，节点 cur 指向 dum。
  2. 循环合并：当 l1 或 l2 为空时跳出；
    1. 当 l1.val < l2.val 时：cur 的后继节点指定为 l1，并 l1 向前走一步；
    2. 当 l1.val ≥ l2.val 时：cur 的后继节点指定为 l2，并 l2 向前走一步；
    3. 节点 cur 向前走一步，即 cur = cur.next。
  3. 合并剩余尾部：跳出时有两种情况，即 l1 为空或 l2 为空。
    1. 若 l1 ≠ null：将 l1 添加至节点 cur 之后；
    2. 否则：将 l2 添加至节点 cur 之后。
  4. 返回值：合并链表在伪头节点 dum 之后，因此返回 dum.next 即可。
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum = new ListNode(0), cur = dum;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dum.next;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5v6htd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(M+N)，空间复杂度：O(1)。

引入伪头节点的做法很妙，代码很精炼，学习学习。

剑指 Offer 52. 两个链表的第一个公共节点

难度：简单

方法一：哈希集合

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set visited = new HashSet();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/liang-ge-lian-biao-de-di-yi-ge-gong-gong-pzbs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(M+N)，空间复杂度：O(M)。

方法二：双指针

设第一个公共节点为 node，链表 headA 的节点数量为 a，链表 headB 的节点数量为 b，两链表的公共尾部的节点数量为 c，则有：

  • 头节点 headA 到 node 前，共有 a - c 个节点；
  • 头节点 headB 到 node 前，共有 b - c 个节点；

考虑构建两个节点指针 A?，B 分别指向两链表头节点 headA，headB，做如下操作：

  • 指针 A 先遍历完链表 headA，再开始遍历链表 headB，当走到 node 时，共走步数为：a + (b - c)
  • 指针 B 先遍历完链表 headB，再开始遍历链表 headA，当走到 node 时，共走步数为：b + (a - c)

如下式所示，此时指针 A，B 重合，并有两种情况：

a + (b - c) = b + (a - c)

若两链表有公共尾部（即 c > 0）：指针 A，B 同时指向第一个公共节点 node。

若两链表无公共尾部（即 c = 0）：指针 A，B 同时指向 null。

另外如果 a 和 b 相等，则第一轮遍历就能找到公共节点或者同时遍历到 null。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/oe95zm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(a+b)（最差也就是两个链表的长度和，长度分别为 M 和 N 时也就是 O(M+N) ），空间复杂度：O(1)。

剑指offer刷题

相关

标签