信长笔记2.0

Appearance

链表常见算法 ​

链表结构 ​

Java
publicclassListNode {
    intval;
    ListNode next;

    ListNode(intx) {
        val = x;
    }

    publicvoidprintList() {
        ListNode node = this;
        while(node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}

使用链表实现LRU ​

缓存清理策略: 先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中，又可以分为两种情况：
  • 如果此时缓存未满，则将此结点直接插入到链表的头部；
  • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
Java
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    //构造方法中指定 accessOrder 为 true ，这样在访问元素时就会把该元素移动到链表尾部，链表首元素就是最近最少被访问的元素；
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    /**
     * 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

单链表反转 ​

  • 核心是维护一个前置指针prev
Java
publicclassLinkedListReversal {
    publicstaticvoidmain(String[] args) {
        // 创建一个简单的链表 1 -> 2 -> 3 -> 4 -> 5
ListNode head = newListNode(1);
        head.next = newListNode(2);
        head.next.next = newListNode(3);
        head.next.next.next = newListNode(4);
        head.next.next.next.next = newListNode(5);

        System.out.println("原始链表:");
        head.printList();

        // 反转链表
ListNode reversedHead = reverseList(head);

        System.out.println("反转后的链表:");
        reversedHead.printList();
    }

    /**
     * 核心是维护一个前向指针prev
     * 时间复杂度O(n), 空间复杂度O(1)
     * @param head
* @return
*/
privatestaticListNode reverseList(ListNode head) {
        ListNode prev = null;
        while(head != null) {
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        returnprev;
    }
}

链表中环的检测（Floyd判圈算法） ​

  • 核心是快慢指针，快的每次移动两节点，慢的每次移动一节点， 若链表成环，则快指针在到达尾节点之前一定会追上慢指针；简单理解，两个人绕操场跑圈，只要一直跑，快的人一定会追上慢的，而且会套一圈
  • 为什么快指针会在慢指针进入环内的第一圈就相遇？

    • 假设环周长为n，链表起点距离环入口为m，第一次相遇时慢指针在环内走过的距离为k，由于快指针走过的距离是慢指针2倍，由于第一次相遇，快指针一定套慢指针一圈，得到**

      $$ 2(m+k)=m+k+n $$

      ，可得 $$ k=n-m $$

      **，由于m>0，因此k<n，因此第一次相遇时慢指针一定未走完一圈

  • 定位环入口？

    • 由上公式同得** $$ m=n-k $$

      **，当两个节点第一次相遇时，由任意一个节点回到起点，然后两个指针以同样的速度移动m个节点，即可相遇，该相遇的节点就是环入口

Java
publicclassLinkedListCycleDetection {
    /**
     * 检测链表中是否有环, 核心是快慢指针
     * 时间复杂度O(n), 空间复杂度O(1)
     *
     * @param head
* @return
*/
publicstaticbooleanhasCycle(ListNode head) {
        if(head == null|| head.next == null) {
            returnfalse; // 空链表或只有一个节点的链表不可能有环
}

        ListNode fast = head;
        ListNode slow = head;
        while(fast != null&& fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast.val == slow.val) {
                returntrue;
            }
        }
        returnfalse;
    }

    // 测试代码
publicstaticvoidmain(String[] args) {
        // 创建一个有环的链表 1 -> 2 -> 3 -> 4 -> 5 -> 3（形成环）
ListNode head = newListNode(1);
        head.next = newListNode(2);
        head.next.next = newListNode(3);
        head.next.next.next = newListNode(4);
        head.next.next.next.next = newListNode(5);
        head.next.next.next.next.next = head.next.next; // 形成环

System.out.println("链表中是否有环: " + hasCycle(head));
    }
}

两个有序的链表合并 ​

Java
publicclassMergeTwoSortedLists {
    /**
     * 合并两个有序链表
     * 时间复杂度O(n+m), 最快的情况下两个链表每个节点都被访问一次
     * 空间复杂度O(1)
     * @param l1
* @param l2
* @return
*/
publicstaticListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个哨兵节点作为结果链表的头结点
ListNode prev = newListNode(0);
        ListNode current = prev;
        // // 当两个链表都不为空时，比较当前节点值，并将较小值加入到结果链表中
while(l1 != null&& l2 != null) {
            if(l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else{
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // 将剩余的节点连接到结果链表后面
if(l1 != null) {
            current.next = l1;
        } else{
            current.next = l2;
        }

        // 返回合并后的链表（不包含哨兵节点）
returnprev.next;
    }

    // 测试代码
publicstaticvoidmain(String[] args) {
        // 创建两个有序链表
ListNode l1 = newListNode(1);
        l1.next = newListNode(3);
        l1.next.next = newListNode(5);

        ListNode l2 = newListNode(2);
        l2.next = newListNode(4);
        l2.next.next = newListNode(6);

        System.out.println("原始链表1：");
        l1.printList();

        System.out.println("原始链表2：");
        l2.printList();

        // 合并两个链表
ListNode mergedList = mergeTwoLists(l1, l2);

        System.out.println("合并后的链表：");
        mergedList.printList();
    }
}

删除链表倒数第n个结点 ​

  • 快慢指针，让第一个节点走n步，然后两个节点一起走，当第一个节点走到末尾时，第二个节点就刚好处于倒数第n个节点
Java
/**
 * 快慢指针
 * @param head
* @param n
* @return
*/
publicstaticListNode removeNthFromEnd(ListNode head, intn) {
    ListNode dummy = newListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;

    for(inti = 0; i <= n; i++) {
        first = first.next;
    }

    while(first != null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;

    returndummy.next;
}

求链表的中间结点 ​

  • 快慢指针，快指针每次走两步，慢指针每次走一步，快指针到尾节点时，慢指针刚好在中间节点
Java
publicstaticListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;

    while(fast != null&& fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    returnslow;
}