考研英语:一下代码的实现逻辑,你知道吗?

最近集中研究了一批链表题。在这里我总结了解决问题的技巧和相应的解决问题的思路。

解题思路不会一丝不苟,主要是总结和分类,希望能用几句话来激发灵感,正确的应该是没有思路时的指导和提纲,以备日后复习。

还有一些经典的话题很重要或者总是头晕,代码的实现逻辑也记录在这里。

一、解决链表问题的两种技巧

遇到链表相关的问题,不管是什么问题,先想想能不能用下面两个技巧。

哨兵节点双指针1、哨兵节点

哨兵节点是一种很常见的链表技巧,可以在处理链表边界问题的情况下降低我们代码的复杂度。主要需要解决的问题如下:

处理完一个链表后,需要返回链表的头节点。我们首先使用一个哨兵节点(虚拟),它的下一个节点指向头节点。只需在最终返回中直接返回 dummy.next 即可。在链表中插入或删除节点时,使用哨兵节点可以简化删除头节点或在头前插入节点时的处理逻辑。遍历链表时,可能需要同时记录前置节点。当你从头节点开始遍历时,头没有前置节点(它为空)。这时引用哨兵节点就相当于帮头节点初始化一个pre节点,可以轻松解决pre节点为空的问题。

由于哨兵节点的使用场景非常广泛,这里不列出典型的话题。

2、双指针

双指针真的很有用。事实上,它不仅是一个链表,而且对于数组问题来说也是一种非常有用的技术。

双指针的主要用途如下:

两个指针在两个链表上行走。快速和慢速指针同时向前和向后移动。前指针先移动 n 步,然后两个指针同时向前移动。两个指针在两个链表上行走。

有时,您需要将两个链表合并为一个链表,或者将一个链表拆分为两个链表。此时就需要使用两个指针在两个链表上行走,进行逻辑处理。

典型主题:

快慢指针

快指针的速度是慢指针的n倍,那么当快指针用完时,慢指针停留的位置是整个链表的1/n(近似位置)。正常情况下,慢指针走一步,快指针走两步。

典型主题:

指针先走 n 步

因为没有办法得到链表的长度,所以对于查找倒数第n个节点的问题,这种方法可以一次遍历找到目标节点。

典型主题:

二、经典链表问题的解决方案 反转链表

206. 反转链表是最经典的链表问题。除了高级问题92.反向链表II,反向链表也将用于其他链表问题的答案,例如上面提到的234.回文链表。

图片[1]-考研英语:一下代码的实现逻辑,你知道吗?-唐朝资源网

反转链表主要有两种解决方案:递归法和迭代法。因为指针容易混淆,所以这里记录标准的解决方案代码。

递归

public ListNode reverseList(ListNode head) {
    // 这个head就是原链表的最后一个节点,也是反转后链表的新节点
    if (head == null || head.next == null) {
        return head;
    }
    // 本质上,resultNode就是递归到最深处后,一层层返回的新链表的头结点
    ListNode resultNode = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return resultNode;
}

迭代法

public ListNode reverseList(ListNode head) {
    ListNode current = head;
    ListNode pre = null;
    ListNode next;
    while (current != null) {
        next = current.next;
        current.next = pre;

        pre = current;
        current = next;
    }
    return pre;
}

LRU 缓存

146. LRU缓存毕竟是缓存,必须是键值对的结构,所以使用了HashMap。

在读写方面,缓存是必需的:get 和 put 函数必须以 O(1).

为了实现这个需求,底层数据结构需要用链表来实现。

所以我们实现的LRU底层数据结构是:HashMap+链表。

代码如下,虽然不优雅,但逻辑很容易理解。

public class LRUCache {
    private int maxSize = 0;
    private Node head = new Node();
    private Node tail = head;
    HashMap map = new HashMap();
    public LRUCache(int capacity) {
        this.maxSize = capacity;

        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // get也是使用了该值,因此需要将该值更新到最近使用的位置
            updateNode(node);
            return node.value;
        }
        return -1;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            updateNode(node);
            return;
        }

图片[2]-考研英语:一下代码的实现逻辑,你知道吗?-唐朝资源网

// 新插入的值放到链尾 Node node = new Node(key, value); node.prev = tail; map.put(key, node); tail.next = node; tail = node; if (map.size() > maxSize) { // 此时需要移除最久未使用数据值 Node removed = head.next; head.next = removed.next; head.next.prev = head; map.remove(removed.key); } } private void updateNode(Node current) { // 如果当前节点已经是尾节点,则不需要移动 if (current.next == null) { return; } // 当前节点的前节点指向当前节点的后节点,即原链表中删除该节点 current.prev.next = current.next; current.next.prev = current.prev; // 当前节点放到尾节点 current.prev = tail; current.next = null; tail.next = current; // 尾节点移动 tail = current; } class Node { public int key; public int value; public Node prev; public Node next; public Node(){} public Node(int key,int value) { this.key = key; this.value = value; } } }

© 版权声明
THE END
喜欢就支持一下吧
点赞40赞赏 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容