链表
算法
|
|
|
198

7081 字
|
57 分钟

链表

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

题目地址：LeetCode

image-20230717225737253

注意：

  • 如果两个链表没有交点，返回null
  • 在返回结果后，两个链表仍须保持原有的结构
  • 可假定整个链表结构中没有循环
  • 程序尽量满足O(n)时间复杂度，且仅用O(1)内存

解题思路：

只有当链表headA和headB都不为空时，两个链表才可能相交。因此首先判断链表headA和headB是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回null

当链表headA和headB都不为空时，创建两个指针pA和pB,初始时分别指向两个链表的头节点headA和headB,然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

  • 每步操作需要同时更新指针pA和pB
  • 如果指针pA不为空，则将指针pA移到下一个节点；如果指针pB不为空，则将指针pB移到下一个节点
  • 如果指针pA为空，则将指针pA移到链表headB的头节点；如果指针pB为空，则将指针pB移到链表headA的头节点
  • 当指针pA和pB指向同一个节点或者都为空时，返回它们指向的节点或者null
/**
     * 通过双指针来辅助查找
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode p1 = headA;
        ListNode p2 = headB;

        while (p1 != p2) {
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }

        return p1;
    }

2. LeetCode 234. 回文链表

题目地址：LeetCode

image-20230718141944439

解题思路：

  1. 创建一个空的整数栈 stack 用于暂存链表节点的值
  2. 创建一个指向输入链表 head 的指针 temp，用于遍历整个链表
  3. 遍历链表，将每个节点的值压入栈中：
    • 使用 while 循环，遍历链表直到 temp 指向最后一个节点为止
    • 在循环中，将当前节点的值 temp.val 压入栈 stack 中，并将 temp 指针指向下一个节点，继续遍历
  4. 再次遍历链表，同时从栈中弹出元素并与链表节点的值进行比较：
    • 使用另一个 while 循环，遍历链表直到 head 为 null，同时检查栈是否为空
    • 在循环中，从栈中弹出栈顶元素，将其与当前链表节点的值进行比较。若不相等，说明链表不是回文的，返回 false
    • 如果比较成功，将 head 指针移动到下一个节点，继续进行下一轮比较
  5. 如果第二个 while 循环能够顺利执行完毕（没有提前返回 false），说明链表中的所有元素都是回文的，返回 true

总结：该解题方法首先利用栈的后进先出特性将链表节点的值压入栈中，然后通过再次遍历链表与栈中元素的比较，判断链表是否为回文结构

/**
     * 全部压栈
     *
     * @param head
     * @return
     */
    public static boolean isPalindromeByAllStack(ListNode head) {
        ListNode temp = head;
        Stack<Integer> stack = new Stack();
        //把链表节点的值存放到栈中
        while (temp != null) {
            stack.push(temp.val);
            temp = temp.next;
        }
        //然后再出栈
        while (head != null) {
            if (head.val != stack.pop()) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

2. 解题思路：

  1. 定义两个指针 slow 和 fast：这两个指针都从链表的头节点 head 开始
  2. 找到链表的中点：
    • 使用 fast 和 slow 指针遍历链表。
    • fast 指针每次移动两个节点，而 slow 指针每次只移动一个节点
    • 当 fast 指针到达链表尾部或者 fast.next 为 null 时，slow 指针就会指向链表的中点
  3. 反转链表的后半部分：
    • 使用 reverse 函数反转从 slow 开始的链表部分
    • 反转后，slow 指针会指向反转链表的头节点
  4. 比较链表的前半部分和反转的后半部分：
    • 同时遍历从 head 开始和从 slow 开始的两个链表
    • 如果所有对应节点的值都相同，那么原链表就是一个回文链表
  5. 返回结果：
    • 如果遍历完所有节点并且所有节点都匹配，返回 true
    • 否则，返回 false
public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

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

        fast = head;
        slow = reverse(slow);

        while(slow != null && slow.val == fast.val){
            slow = slow.next;
            fast = fast.next;
        }
        return slow == null ? true : false;

    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

3. LeetCode 21. 合并两个有序链表

题目地址：LeetCode

image-20230718143741579

解题思路：

  1. 创建一个虚拟头节点 preHead 作为合并后链表的起始点，并创建一个当前节点指针 preNode 初始化指向 preHead
  2. 使用 while 循环，遍历两个有序链表 list1 和 list2，直到其中一个链表为空
  3. 在循环中，比较 list1 和 list2 当前节点的值，将较小的节点接入合并链表，并将相应的链表指针向后移动
  4. 更新 preNode 指向新接入的节点，使其指向合并链表的最后一个节点
  5. 循环结束后，其中一个链表已经遍历完毕，可能还有一个链表中的节点未处理完毕。此时，直接将剩余未处理的链表部分接入合并链表的末尾
  6. 返回 preHead.next，即合并后的有序链表的起始节点
/**
     * 虚拟头结点和双指针
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode preHead = new ListNode(-1);
        ListNode preNode = preHead;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                preNode.next = list1;
                list1 = list1.next;
            } else {
                preNode.next = list2;
                list2 = list2.next;
            }
            preNode = preNode.next;
        }
        preNode.next = list1 == null ? list2 : list1;

        return preHead.next;
    }

合并K个有序链表

/**
     * 合并K个有序链表
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for (ListNode list : lists) {
            res = mergeTwoLists(res, list);
        }
        return res;
    }

4. LeetCode 1669. 合并两个链表

题目地址：LeetCode

image-20230718162856232

解题思路：

  1. 找到list2的尾结点
    • 将list2的头节点赋值给list2End
    • 使用循环遍历list2直到最后一个节点，同时更新list2End的值
  2. 寻找需要替换的区间[a, b]在list1中的位置
    • 初始化两个指针p1和p2为list1的头节点
    • 使用循环将p1移动到下标为a - 1的位置，将p2移动到下标为b + 1的位置
  3. 合并list1和list2
    • 将list2接在list1的前一个节点p1之后，即p1.next = list2
    • 将list2End的后继节点接在list1的后一个节点p2之前，即list2End.next = p2
  4. 返回合并后的链表list1
/**
     * 合并两个链表
     *
     * @param list1
     * @param a
     * @param b
     * @param list2
     * @return
     */
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        // 1. 找到list2的尾结点
        ListNode list2End = list2;
        while (list2End.next != null) {
            list2End = list2End.next;
        }
        // 2. 寻找[a,b]区间
        ListNode p1 = list1;
        ListNode p2 = list1;
        // 2.1. 找到list1下标为a的前一个结点
        for (int i = 0; i < a - 1; i++) {
            p1 = p1.next;
        }
        // 2.2. 找到list1下标为b的后一个结点
        for (int i = 0; i < b + 1; i++) {
            p2 = p2.next;
        }
        // 3. 合并list1和list2
        list2End.next = p2;
        p1.next = list2;
        return list1;
    }

5. LeetCode 876. 链表的中间结点

题目地址：LeetCode

image-20230719084432412

解题思路：

  1. 初始化两个指针 slow 和 fast，它们都指向链表的头节点 head
  2. 在循环中，同时移动 slow 和 fast 指针。每次迭代，slow 指针向前移动一步，而 fast 指针向前移动两步
  3. 循环的条件是 fast 不为 null 并且 fast.next 不为 null。这样做的目的是确保在每次迭代时，fast 指针都至少能够移动两步，避免出现空指针异常
  4. 当 fast 到达链表末尾时，即 fast 为 null 或者 fast.next 为 null，循环结束
  5. 最终返回 slow 指针的位置，即链表的中间节点。由于 fast 指针每次移动两步，而 slow 指针每次移动一步，所以当循环结束时，slow 指针正好指向链表的中间节点

这种快慢指针法的原理在于，快指针的速度是慢指针的两倍，所以当快指针到达链表末尾时，慢指针刚好在链表的中间位置

/**
     * 快慢指针
     *
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

6. 寻找倒数第K个元素

题目地址：LeetCode

image-20231211163946896

解题思路：

  1. 先将fast向后遍历到第k+1个节点，slow仍然指向链表的第一个节点，此时指针fast与slow二者之间刚好间隔k个节点
  2. 之后两个指针同步向后走，当fast走到链表的尾部空节点时，slow指针刚好指向链表的倒数第k个节点
/**
     * 寻找倒数第K个元素
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

7. LeetCode 61. 旋转链表

题目地址：LeetCode

image-20230719141104100

解题思路：

  1. 首先检查输入的链表是否为空（head == null）或者k是否为0。如果是其中之一，直接返回原链表，因为旋转0次或者对空链表旋转没有任何变化
  2. 定义三个指针变量：temp、slow、fast，它们都初始化为链表的头节点head。其中，temp用于最后返回结果，slow和fast用于找到旋转后的新头节点
  3. 使用一个循环遍历链表，计算链表的长度len。此时head指针被移动到了链表的尾部，用于后续的操作
  4. 如果k是链表长度len的倍数，说明旋转后的链表和原链表相同，因此直接返回原链表head
  5. 如果k不是链表长度len的倍数，则需要进行旋转操作。首先，通过一个循环将fast指针向后移动k次，即找到旋转后的新头节点的前一个节点
  6. 接下来，使用两个指针slow和fast一起移动，直到fast指针指向链表的最后一个节点。此时slow指针指向旋转后的新头节点的前一个节点
  7. 将slow的下一个节点作为新的头节点，将fast的next指针指向原链表的头节点，实现链表的旋转
  8. 最后，返回新的头节点，即res
/**
     * 旋转链表
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        // 1. 判断链表是否为空或k是否为0
        if (head == null || k == 0) {
            return head;
        }
        // 2. 定义所需变量结点
        ListNode temp = head;
        ListNode slow = head;
        ListNode fast = head;
        int len = 0;
        // 3. 求出链表长度
        while (head != null) {
            head = head.next;
            len++;
        }
        // 4. k如果是链表长度的倍数则相当于没移，直接返回
        if (k % len == 0) {
            return temp;
        }
        // 5. 先让快指针走k步
        while ((k % len) > 0) {
            fast = fast.next;
            k--;
        }
        // 6. 快慢指针一起移动，知道快指针移到最后一个结点
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 7. 拼接链表
        ListNode res = slow.next;
        slow.next = null;
        fast.next = temp;
        // 8. 返回
        return res;
    }

8. LeetCode 203. 移除链表元素

题目地址：LeetCode

image-20230720085958030

解题思路：

  1. 创建一个虚拟头节点 dummyHead，将它的 next 指针指向原链表的头节点 head
  2. 初始化一个指针 cur，指向虚拟头节点 dummyHead
  3. 遍历链表，循环条件是 cur.next 不为空，即 cur 不是链表的最后一个节点
  4. 在循环中，检查 cur.next 节点的值是否等于给定的值 val。如果相等，说明需要删除该节点，直接将 cur.next 指针跳过当前节点，指向当前节点的下一个节点（即删除当前节点）
  5. 如果 cur.next 节点的值不等于给定的值 val，则说明当前节点不需要删除，将 cur 指针向后移动一个节点，继续下一轮循环。
  6. 循环结束后，链表中所有值为 val 的节点都被删除了
  7. 返回处理后的链表头节点，即为 dummyHead.next，作为最终结果
/**
     * 删除特定值元素
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;

        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }

9. LeetCode 19. 删除链表的倒数第 N 个结点

题目地址：LeetCode

image-20230720093117957

解题思路：

  1. 创建一个虚拟头节点 dummyHead，将其 next 指针指向链表的头节点 head。这样做是为了方便处理头节点的删除情况
  2. 初始化两个指针 slow 和 fast，slow指向虚拟头节点 dummyHead、fast指向头结点head
  3. 移动 fast 指针，使其先走 N 步。这样，fast 和 slow 之间就相隔 N 个节点
  4. 然后，同时移动 fast 和 slow 指针，直到 fast 指针指向链表末尾（即 fast.next 为 null）
  5. 此时，slow 指针指向倒数第 N+1 个节点
  6. 修改 slow.next 指针，使其指向倒数第 N+1 个节点的下一个节点，即跳过倒数第 N 个节点，从而实现删除倒数第 N 个节点
  7. 返回虚拟头节点的 next 指针，即为最终的链表头节点，表示完成删除操作后的链表
/**
     * 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;

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

        return dummyHead.next;
    }

10. LeetCode 83. 删除排序链表中的重复元素

题目地址：LeetCode

image-20230721090136913

解题思路：

  1. 首先，检查输入的链表头节点是否为null，如果是空链表，则直接返回该头节点null
  2. 如果链表不为空，就从头节点开始遍历链表。使用一个指针cur来代表当前遍历到的节点，开始时指向头节点head
  3. 在遍历过程中，对于每个节点cur，检查其后继节点cur.next是否存在，即cur是否为链表中的最后一个节点。如果cur.next存在，继续执行下面的步骤，否则表示已经遍历到了链表末尾，可以结束遍历
  4. 检查当前节点cur的值cur.val和它的后继节点cur.next的值是否相等。如果相等，说明该节点是重复元素，因为链表是有序的，所以连续重复的元素会相邻。为了删除重复元素，只需要将当前节点cur的next指针指向其后继节点cur.next的next节点，即跳过一个重复元素，相当于删除了重复元素。这里的操作是 cur.next = cur.next.next
  5. 如果当前节点cur的值cur.val和后继节点cur.next的值不相等，表示当前节点不是重复元素，直接将指针cur移动到下一个节点，即 cur = cur.next;，继续遍历
  6. 重复执行步骤3至步骤5，直到遍历到链表末尾为止
  7. 最后，返回删除重复元素后的链表的头节点head，即可得到链表中没有重复元素的链表
/**
     * 删除链表中的重复元素,保留一个
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

11. LeetCode 82. 删除排序链表中的重复元素 II

题目地址：LeetCode

image-20230721092028149

解题思路：

  1. 首先，检查输入的链表头节点是否为null，如果是空链表，则直接返回该头节点null

  2. 创建一个虚拟头节点(dummyHead)。将虚拟头节点的next指针指向原链表的头节点head，以便处理链表开头的重复元素情况

  3. 使用指针cur来代表当前遍历到的节点，开始时指向虚拟头节点dummyHead

  4. 在遍历过程中，对于每个节点cur，检查其后继节点cur.next和后继节点的后继节点cur.next.next是否存在，即cur是否至少为链表中的倒数第二个节点。如果cur.next和cur.next.next都存在，继续执行下面的步骤，否则表示已经遍历到了链表倒数第二个节点或更短的链表，可以结束遍历

  5. 检查当节点cur.next的值cur.next.val和它的后继节点cur.next.next.val是否相等。如果相等，说明链表中存在重复元素。为了删除所有重复元素，需要进入一个循环，将指针cur的next指向不等于x的下一个节点，直到cur的next指向的节点值不等于x。这里的操作是：

    int x = cur.next.val;
while (cur.next != null && cur.next.val == x) {
   cur.next = cur.next.next;
}

  6. 如果当前节点cur的值cur.next.val和后继节点cur.next.next.val不相等，表示当前节点cur的后继节点cur.next是唯一的，不是重复元素，直接将指针cur移动到下一个节点，即 cur = cur.next;，继续遍历

  7. 重复执行步骤4至步骤6，直到遍历到链表倒数第二个节点为止

  8. 最后，返回虚拟头节点dummyHead的next指针所指向的链表头节点，即可得到删除所有重复元素的链表

/**
     * 删除链表中的重复元素,全都不要
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;

        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }

12. LeetCode 206. 反转链表

题目地址：LeetCode

image-20230722091010803

1. 解题思路：

  1. 创建虚拟头结点：首先，创建一个名为dummyHead的虚拟头结点，它将充当反转后链表的新头结点。虚拟头结点的值设置为-1，但它不包含任何实际数据
  2. 遍历原链表：然后，代码使用cur指针来遍历原始链表head
  3. 反转操作：在每次遍历中，将cur指向的节点从原链表中取下，并将其插入到虚拟头结点之后，成为反转后链表的新头结点
  4. 更新指针：进行插入操作时，先将cur.next指针暂存为next，然后将cur.next指向虚拟头结点的下一个节点，再将虚拟头结点的next指针指向cur，最后将cur指向暂存的next，继续遍历原链表
  5. 完成反转：当遍历完原链表后，虚拟头结点的next指针指向的节点就是反转后链表的新头结点
  6. 返回结果：最后，返回反转后链表的头结点，即dummyHead.next

image-20230722094932065

/**
     * 方法1：带虚拟头结点
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = dummyHead.next;
            dummyHead.next = cur;
            cur = next;
        }

        return dummyHead.next;
    }

2. 解题思路：

  1. 初始化指针：首先，创建两个指针pre和cur，分别用于记录前一个节点和当前节点。开始时，pre为null，cur指向原链表的头结点head
  2. 遍历原链表：通过循环遍历原链表，从头结点一直遍历到末尾节点。在每次循环中，执行反转操作
  3. 反转操作：在每次循环中，首先将当前节点cur的下一个节点暂存为next，然后将cur.next指向pre，将当前节点指向的下一个节点指向前一个节点，实现反转操作
  4. 更新指针：完成反转操作后，需要将指针向前移动。将pre指向当前节点cur，将cur指向暂存的下一个节点next，继续遍历原链表
  5. 完成反转：当遍历完原链表后，pre指针所指的节点就是反转后链表的头结点
  6. 返回结果：最后，返回反转后链表的头结点，即pre

image-20230722095006376

/**
     * 方法2：不带虚拟头结点
     *
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }

12. LeetCode 92. 反转链表 II

题目地址：LeetCode

image-20230724084751031

解题思路：

image-20230724095608626

image-20230724095641164

/**
     * 带虚拟头结点指定区间反转链表
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;

        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return dummyHead.next;
    }

14. LeetCode 141. 环形链表

题目地址：LeetCode

image-20231016212611706

1. 解题思路：

  1. 初始化：创建一个集合来存储链表中已经访问过的节点
  2. 遍历链表：
    • 对于链表中的每一个节点，检查它是否已经在集合中
    • 如果当前节点已存在于集合中，说明链表中存在环，立即返回 true
    • 如果当前节点不在集合中，将其添加到集合，并继续检查下一个节点
  3. 结束：如果整个链表都遍历完毕，并且没有发现环，那么返回 false，表示链表中没有环
public boolean hasCycle(ListNode head) {
        ListNode pNode = head;
        Set<ListNode> set = new HashSet<>();

        while(pNode != null){
            if(set.contains(pNode)){
                return true;
            } else{
                set.add(pNode);
            }
            pNode = pNode.next;
        }
        return false;
    }

2. 解题思路：

  1. 基础检查：如果链表为空或只有一个节点，那么它肯定没有环，直接返回 false
  2. 初始化：创建两个指针，一个快指针 fast 和一个慢指针 slow，都指向链表的头节点 head
  3. 遍历链表：
    • 使用一个循环，条件是 fast 指针和 fast.next 都不为 null
    • 在每次循环中，slow 指针移动到下一个节点，而 fast 指针移动到下下个节点
    • 如果在某次循环中，slow 和 fast 指针指向同一个节点，说明链表中存在环，返回 true
  4. 结束：如果循环结束并且没有发现环，返回 false
public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }

15. LeetCode 142. 环形链表 II

题目地址：LeetCode

image-20231016222840637

解题思路：

  1. 初始化两个指针，一个叫做 slow，另一个叫做 fast，它们都指向链表的头节点
  2. 进入一个循环，其中 fast 每次前进两步，而 slow 每次前进一步
  3. 在循环中，检查 fast 和 fast.next 是否为空，以避免出现 NullPointerException。如果 fast 或 fast.next 为空，说明链表没有环，直接返回 null
  4. 如果 fast 和 slow 指针在循环内相遇（即 slow == fast），说明链表中存在环。此时，将 fast 指针重新设置为链表头部，以便从头开始查找环的起始节点
  5. 进入第二个循环，其中 slow 和 fast 指针都每次前进一步，直到它们再次相遇。这时，它们相遇的节点就是环的起始节点
  6. 返回找到的环的起始节点
public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while(true){
            if(fast == null || fast.next == null) return null;
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                fast = head;
                break;
            }
        }
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

16. LeetCode 24. 两两交换链表中的节点

题目地址：LeetCode

image-20231018163444723

解题思路：

image-20231213223035631

  1. 初始化：
    • 创建一个虚拟头节点 dummyHead，并将其 next 指针指向原链表的头节点 head
    • 创建一个临时节点 pre，并将其设置为虚拟头节点 dummyHead
    • 创建一个临时节点 cur，并将其设置为头节点 head
  2. 循环交换：
    • 使用一个 while 循环，条件是 cur.next 和 cur.next 都不为 null
    • 在每次循环中，保存当前节点 cur 的下一个节点 next
  3. 节点交换：
    • 将 cur.next 指向 next.next
    • 将 next.next 指向 cur
    • 将 pre.next 指向 next
  4. 更新临时节点：
    • 更新 pre 为 cur，cur = cur.next
  5. 返回结果：
    • 返回 dummyHead.next，即交换后链表的头节点
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        ListNode cur = head;

        while(cur != null && cur.next != null){
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = cur;
            pre.next = next;
            pre = cur;
            cur = cur.next;
        }
        return dummyHead.next;
    }
}

17. LeetCode 369. 单链表+1

题目地址：LeetCode

用一个非空单链表来表示一个非负整数，然后将这个整数加一。你可以假设这个整数除了 0 本身，没有任何前导的 0。这个整数的各个数位按照高位在链表头部、低位在链表尾部的顺序排列

示例：

输入: [1,2,3]   
输出: [1,2,4]

解题思路：

  1. 先把题目给出的链表遍历放到栈中

  2. 从栈中弹出栈顶数字 digit，计算 adder 之和（adder 在初始化的时候是 1，之后都是 0；表示链表与 1 相加），再加上进位 carry，得到当前位置的和 sum

    • 如果 sum >= 10 ，那么进位 carry = 1 ，当前位设置为 sum - 10
    • 如果 sum < 10，那么进位 carry = 0，当前位设置为 sum

  3. 设置新链表节点，其值为 sum，逆序拼接成链表即可

  1. 为什么要有 carry > 0：
    • 这是为了处理进位的情况。例如，如果链表表示的数字是 999，加 1 后会变成 1000，这会导致一个新的节点需要被添加到链表的头部。在这种情况下，carry 会是 1，即使栈已经为空，循环仍需要继续以处理这个进位
  2. 为什么每次进循环判断栈是否为空：
    • 这是因为即使栈为空，仍然可能存在进位（carry > 0）需要处理。如果仅在 while 循环的条件中判断栈是否为空，那么一旦栈为空，循环就会立即终止，这样就无法处理可能存在的进位
    • 通过在循环体内部进行判断，代码可以更灵活地处理这两种情况（即栈为空和存在进位）
public ListNode plusOne(ListNode head) {
        Stack<Integer> st = new Stack<>();
        while(head != null){
            st.push(head.val);
            head = head.next;
        }

        int carry = 0;
        ListNode dummyHead = new ListNode(-1);
        int adder = 1;

        while(!st.empty() || carry > 0){
            int digit = st.empty() ? 0 : st.pop();
            int sum = digit + adder + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = sum >= 10 ? sum -10 : sum;
            ListNode cur = new ListNode(sum);
            cur.next = dummyHead.next;
            dummyHead.next = cur;
            adder = 0;
        }

        return dummyHead.next;
    }

18. LeetCode 445. 两数相加 II

题目地址：LeetCode

image-20231019110913045

解题思路：

  1. 首先，将两个输入链表 l1 和 l2 进行反转，这样可以从低位到高位逐位相加
  2. 创建一个虚拟头节点 dummyHead 和一个当前节点 cur，并初始化进位变量 carry 为0
  3. 使用一个循环来遍历两个链表，直到两个链表都遍历完为止。在每一轮循环中，将进位值 carry 与当前节点的值相加，如果链表 l1 还有节点，就将节点值加到 val 中，然后移动 l1 指针，如果链表 l2 还有节点，也将节点值加到 val 中，然后移动 l2 指针
  4. 创建一个新节点，其值为 val % 10（因为每个节点的值应该在0到9之间），并将这个新节点连接到结果链表的尾部（通过 cur.next）
  5. 更新进位值 carry 为 val / 10，以便在下一轮循环中使用
  6. 继续循环，直到两个链表都遍历完。如果最后还有进位值 carry 大于0，创建一个新节点表示进位，并连接到结果链表的尾部
  7. 最后，返回结果链表，但需要将结果链表再次反转，以得到正确的结果
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);

        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        int carry = 0;

        while(l1 != null || l2 != null){
            int val = carry;
            if(l1 != null){
                val += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                val += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(val % 10);
            carry = val / 10;
            cur = cur.next;
        }

        if(carry > 0){
            cur.next = new ListNode(carry);
        }
        return reverse(dummyHead.next);
    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

19. LeetCode 25. K 个一组翻转链表

题目地址：LeetCode

image-20231020204052858

解题思路：

  1. 初始化指针和哑节点（dummy node）：
    • 创建一个哑节点 dummyHead，并让其 next 指向链表的头节点 head
    • 初始化两个指针 pre 和 end，都指向 dummyHead
  2. 找到需要翻转的子链表：
    • 使用 end 指针向前移动 k 个节点，以找到需要翻转的子链表的末尾
    • 如果 end 为 null，则跳出循环
  3. 翻转子链表：
    • 记录子链表的头节点 start 和下一个节点 next
    • 断开子链表和后面节点的连接（end.next = null）
    • 翻转子链表，并将 pre.next 指向翻转后的子链表的头节点
  4. 重新连接翻转后的子链表：
    • 将翻转后的子链表的尾节点（即翻转前的 start）连接到 next
    • 更新 pre 和 end 指针，使其指向新的子链表的尾节点
  5. 返回结果：
    • 最后，返回 dummyHead.next，即翻转后的链表的头节点
  1. 新建一个虚拟头结点，之后直接遍历，根据是否为K个找到四个关键位置，并用变量pre、start、end和next标记，如下：

image.png

  1. 将end.next = null，蓝色部分可以直接复用前面红色反转的方法来完成反转。注意上图中指针的指向和几个变量的位置，head表示传给反转方法的参数，结构如下所示：

image.png

  1. 完成之后，我们要将裁下来的部分再缝到原始链表上，这就需要调整指针指向了，同样注意指针的指向：

image.png

  1. 最后调整一下几个变量的位置，为下一次做准备：

image.png

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode pre = dummyHead;
        ListNode end = dummyHead;

        while(end.next != null){
            for(int i = 0; i < k && end != null; i++) end = end.next;
            if(end == null) break;

            ListNode start = pre.next;
            ListNode next = end.next;

            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = pre;
        }
        return dummyHead.next;

    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

20. LeetCode 146. LRU 缓存

题目地址：LeetCode

image-20231020213209957

解题思路：

  • 对于 get 操作，首先判断 key 是否存在：

    • 如果 key 不存在，则返回 −1

    • 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值

  • 对于 put 操作，首先判断 key 是否存在：

    • 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项

    • 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部

class LRUCache {

    class DLinkedNode{
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode next;
        public DLinkedNode(){}
        public DLinkedNode(int _key, int _value){
            key = _key;
            value = _value;
        }
    }

    private Map<Integer,DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head,tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if(node == null) return -1;
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if(node == null){
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key,value);
            // 添加进哈希表
            cache.put(key,newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            size++;
            if(size > capacity){
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                size--;
            }
        } else{
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }

    }

    private void addToHead(DLinkedNode node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail(){
        DLinkedNode end = tail.pre;
        removeNode(end);
        return end;
    }
}
🌟 如果您喜欢我的文章，欢迎赞赏支持，您的支持是我创作的最大动力！🌟
🖋 作者：Enndfp
🔗链接：https://blog.enndfp.cn
📜版权声明：您可以自由转载，但请务必注明原文地址，感谢您的尊重与支持~
算法
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
队列和Hash

							
							

							
二叉树

							
							

							
栈

							
							

							
数组