链表-双指针-虚拟节点-力扣

这篇具有很好参考价值的文章主要介绍了链表-双指针-虚拟节点-力扣。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

力扣 142 环形链表求循环起点 重点

链表-双指针-虚拟节点-力扣,华为od题库/力扣题库/labuladong算法笔记学习,链表,leetcode,数据结构,双指针文章来源地址https://www.toymoban.com/news/detail-851907.html

/*力扣142 环形链表II
     * 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
     * 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
     * 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
     * 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
     * 不允许修改 链表。*/
    public static ListNode detectCycle(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        ListNode newHead = dummy;
        boolean symbol = false;

        while (fast != null && fast.next != null) {
            // 注意 Fast和Fast.next 都不为 null
            // 否则 Fast.next.next 会报空指针错误
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                //若能相等则 有环
                // slow 走K步 fast走K步
                // K = t + nS + M
                // 2K = t + mS + M
                // 非循环距离: t
                // 循环周长 :  S
                // 循环起点距离相遇点: M
                // 则 相遇 意味着有环 意味着 K = (m-n)S
                // 则 在Fast不再动的情况下 slow 再走 K 步 依然在这个相遇点
                // 则 其走K-M步一定在循环起点
                // 同理 在slow走第二个K的时候同时设置一个新的指针从头结点开始也走K-M步
                // 则两者应该再循环起点相遇
                symbol = true;
                break;
            }
        }
        if (symbol) {
            // 有环
            // slow走K-M步 fast不动 newHead 走K-M步
            // newHead 与 slow 在循环起点 重合
            while (newHead != slow) {
                newHead = newHead.next;
                slow = slow.next;
            }
            // newHead == slow
            return newHead;
        } else {
            // 无环
            return null;
        }
    }

力扣 21 合并两个有序链表

/*1、合并两个有序链表
         力扣 21
            将两个升序链表合并为一个新的 升序 链表并返回。
            新链表是通过拼接给定的两个链表的所有节点组成的
            两个链表的节点数目范围是 [0, 50]
            -100 <= Node.val <= 100
            l1 和 l2 均按 非递减顺序 排列
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        // 设置虚拟头结点
        ListNode p = dummy;
        //p和dummy都是存储同一个对象地址
        ListNode p1 = l1, p2 = l2;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
                p = p.next;
            } else {
                p.next = p2;
                p2 = p2.next;
                p = p.next;
                // p要向前进
            }
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }

力扣 86 分割链表

/*
     * 给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,
     * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     * 你应当 保留 两个分区中每个节点的初始相对位置。*/
    public static ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);

        ListNode h = head;
        ListNode p1 = dummy1;
        ListNode p2 = dummy2;

        while (h != null) {
            if (h.val < x) {
                p1.next = h;
                // 向dummy1 的链表尾部添加 h节点
                h = h.next;
                // head 链表向后走一步
                p1 = p1.next;
                // p1 指向 dummy1链表末尾节点
                p1.next = null;
                // p1 末尾的next 设置为 null
            } else {
                p2.next = h;
                h = h.next;
                p2 = p2.next;
                p2.next = null;
            }
        }
        p1.next = dummy2.next;
        return dummy1.next;
    }

力扣23 合并K个有序链表 – 优先队列(二叉堆 小顶堆)重点

/*给你一个链表数组,每个链表都已经按升序排列。
    请你将所有链表合并到一个升序链表中,返回合并后的链表。*/
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length < 1) {
            // 如果用 < 1 的值创建优先队列 则会产生异常
            // IllegalArgumentException - if initialCapacity is less than 1
            return null;
        } else {
            PriorityQueue<ListNode> priorityQueue = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {
                @Override
                public int compare(ListNode o1, ListNode o2) {
                    return o1.val - o2.val;
                }
            });
            // 优先级队列(二叉堆)  设置为最小堆  队列长度为lists的元素个数  有K个链表 传入 K 为队列长度

            ListNode dummy = new ListNode(-1); // 设置虚拟头结点 等待最后返回dummy.next
            ListNode p = dummy;

            for (ListNode listNode : lists) {
                if (listNode != null) {
                    priorityQueue.add(listNode);
                    // 如果 此链表不为空 则将头结点 存入最小堆的优先队列
                }
            }
            while (!priorityQueue.isEmpty()) {
                // 当优先队列内元素个数不为空 时
                ListNode temp = priorityQueue.poll();// temp 指向 队列头元素 同时队头出队
                p.next = temp;
                p = p.next;
                if (temp.next != null) {
                    priorityQueue.add(temp.next); // 刚出队的链表的下一个元素 进入队列
                }
            }
            return dummy.next;
        }
    }

力扣19 找倒数第N个元素 快慢指针 + 一次遍历 重点

/*力扣19 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
     * 要求: 只遍历一次结点 思路:两个指针一个在前一个在后
     * 因为要往前走N步 设置虚拟头结点的情况下 代码更清楚简洁 不必要多判断
     * 只有一个元素的情况(因为如果不用虚拟头结点的话, 只有一个元素时起始节点就在此)*/
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 题目默认head不为空 链表元素个数>=1
        // 先要找到倒数 第N个节点
        ListNode dummy = new ListNode(-1);
        // 设置虚拟头结点 方便向前走N步
        dummy.next = head;
        ListNode p1 = dummy;
        ListNode p2 = dummy;

        for (int i = 0; i < n; i++) {
            p1 = p1.next;
            // 向前走N步
        }
        if (p1 == null) {
            return null;
            // 链表不够长 总数都不够N
        }
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 当 p1 为 末尾元素时 退出循环
        // 此时 p2.next 指向 倒数第N个元素
        ListNode p3 = p2.next.next;
        p2.next = p3;
        // 删除倒数第N个元素

        return dummy.next;
    }

力扣876 快慢指针找中间节点

/*力扣876
    给你单链表的头结点 head ,请你找出并返回链表的中间结点。
    如果有两个中间结点,则返回第二个中间结点。
    思路: 虚拟节点 + 快慢指针 快的一次走两步 慢的一次走一步
          当快的指向空的时候 慢的刚好在中间节点的位置(同时适用于奇数个元素和偶数个元素的情况)*/
    public static ListNode middleNode(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p1 = dummy;
        ListNode p2 = dummy;

        while (p1 != null) {
            p2 = p2.next;
            // 奇数个元素时 最后一步走之前 p1.next != null && p1.next.next == null 成立
            // 偶数个元素时 最后一步走之前 p1.next == null 成立
            // 所以 让p1=p1.next.next 为一大步 的情况下
            // 偶数个的情况下不能走最后一大步所以下面用了break
            // 但P2 必须要走这一步
            if (p1.next == null) {
                break;
            } else {
                p1 = p1.next.next;
            }
        }
        return p2;
    }

力扣 160 相交链表 遍历“两遍”

/*
     * 力扣160 相交链表
     * 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。
     * 如果两个链表不存在相交节点,返回 null 。
     * 思路:两个指针同步向前走  A走到末尾之后下一步走B的头部,B走到末尾之后下一步走到A的头部
     * 则 两个指针会同时在第一个合并节点处同步到达 p==q 退出循环
     * 如果没有共同部分 则 会同时到null 依然满足p==q 退出循环 */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         /*
        很奇怪 我用虚拟头结点 就超时 放弃用虚拟头结点就通过力扣测试
        
        // 若用虚拟头结点 则要大量使用 p.next 而我们要 在末尾 重新转入 另一个链表表头
        // 故在转入的时候 不要用next 防止篡改 链表 导致死循环
        ListNode dummy = new ListNode(-1);
        dummy.next = headA;
        ListNode dummy2 = new ListNode(-1);
        dummy2.next = headB;

        ListNode p = dummy;
        ListNode q = dummy2;

        while (p != q) {
            if (p.next == null) {
                // 将P的位置改变 而不改变原链表结构
                p = headB;
            }
            if (q.next == null) {
                // 将Q的位置改变 而不改变原链表结构
                q = headA;
            }
            p = p.next;
            q = q.next;
        }
        return p;*/

        ListNode p = headA;
        ListNode q = headB;
        while (p != q) {
            if (p == null) {
                // 将P的位置改变 而不改变原链表结构
                p = headB;
            } else {
                p = p.next;
            }
            if (q == null) {
                // 将Q的位置改变 而不改变原链表结构
                q = headA;
            } else {
                q = q.next;
            }
        }
        return p;
    }

辅助测试类

package com.caoii.LinkedList;

public class ListNode {
    public int val;
    public ListNode next;

    ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
package com.caoii;/*
 *@program:labu-pratice-study
 *@package:com.caoii
 *@author: Alan
 *@Time: 2024/4/14  11:38
 *@description: 双指针解决链表问题相关应用的测试
 */

import com.caoii.LinkedList.DoublePointerInLinkedList;
import com.caoii.LinkedList.ListNode;
import org.junit.jupiter.api.Test;

public class DoublePointerTest {

    /*力扣21 有序链表合并*/
    @Test
    public void test_01() {
        ListNode l1 = new ListNode(1);
        ListNode p1 = l1;
        p1.next = new ListNode(2);
        p1 = p1.next;
        p1.next = new ListNode(4);

        ListNode l2 = new ListNode(1);
        ListNode p2 = l2;
        p2.next = new ListNode(3);
        p2 = p2.next;
        p2.next = new ListNode(9);

        ListNode returnListNode = DoublePointerInLinkedList.mergeTwoLists(l1, l2);
        ListNode p = returnListNode;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
        System.out.println();
    }

    /*力扣86 将一个链表分割成两个链表再合并*/
    @Test
    public void test_02() {
        ListNode l1 = new ListNode(1);
        ListNode p1 = l1;
        p1.next = new ListNode(4);
        p1 = p1.next;
        p1.next = new ListNode(3);
        p1 = p1.next;
        p1.next = new ListNode(2);
        p1 = p1.next;
        p1.next = new ListNode(5);
        p1 = p1.next;
        p1.next = new ListNode(2);


        ListNode returnListNode = DoublePointerInLinkedList.partition(l1, 3);
        ListNode p = returnListNode;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
        System.out.println();
    }

    /*力扣 23 合并K个有序链表*/
    @Test
    public void test_03() {
        ListNode l1 = new ListNode(1);
        ListNode p1 = l1;
        p1.next = new ListNode(4);
        p1 = p1.next;
        p1.next = new ListNode(5);

        ListNode l2 = new ListNode(1);
        ListNode p2 = l2;
        p2.next = new ListNode(3);
        p2 = p2.next;
        p2.next = new ListNode(4);

        ListNode l3 = new ListNode(2);
        ListNode p3 = l3;
        p3.next = new ListNode(6);


        ListNode[] lists = new ListNode[]{
                l1, l2, l3
        };
        ListNode returnListNode = DoublePointerInLinkedList.mergeKLists(lists);
        ListNode p = returnListNode;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
        System.out.println();
    }


    /*力扣19 一次遍历 删除倒数第N个元素 */
    @Test
    public void test_04() {
        ListNode l1 = new ListNode(1);
        ListNode p1 = l1;
        p1.next = new ListNode(2);
        p1 = p1.next;
        p1.next = new ListNode(3);
        p1 = p1.next;
        p1.next = new ListNode(4);
        p1 = p1.next;
        p1.next = new ListNode(5);

        ListNode returnListNode = DoublePointerInLinkedList.removeNthFromEnd(l1, 2);
        ListNode p = returnListNode;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
        System.out.println();
    }

    /*力扣876 找链表的中间节点 奇数个找中间 偶数个找中间两个的后一个 */
    @Test
    public void test_05() {
        ListNode l1 = new ListNode(1);
        ListNode p1 = l1;
        p1.next = new ListNode(2);
        p1 = p1.next;
        p1.next = new ListNode(3);
        p1 = p1.next;
        p1.next = new ListNode(4);
        p1 = p1.next;
        p1.next = new ListNode(5);
        p1 = p1.next;
        p1.next = new ListNode(6);

        ListNode returnListNode = DoublePointerInLinkedList.middleNode(l1);
        ListNode p = returnListNode;
        // 输出从中间节点开始的后半截
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
        System.out.println();
    }

    /*力扣142 环形链表求循环起点 */
    @Test
    public void test_06() {
        ListNode l1 = new ListNode(3);
        ListNode p1 = l1;
        p1.next = new ListNode(2);
        p1 = p1.next;
        ListNode temp = p1;
        // temp 辅助形成循环链表
        p1.next = new ListNode(0);
        p1 = p1.next;
        p1.next = new ListNode(-4);
        p1 = p1.next;
        p1.next = temp;
        // 形成循环链表

        ListNode returnListNode = DoublePointerInLinkedList.detectCycle(l1);
        ListNode p = returnListNode;
        System.out.println("循环起点的值:" + p.val);
    }

    /*力扣160 相交链表求第一个交点 */
    @Test
    public void test_07() {
        ListNode l1 = new ListNode(-3);
        ListNode l2 = new ListNode(30);
        ListNode p1 = l1;
        ListNode p2 = l2;

        ListNode temp = new ListNode(300);
        ListNode p3 = temp;
        p3.next = new ListNode(400);
        p3 = p3.next;
        p3.next = new ListNode(500);
        p3 = p3.next;


        p1.next = new ListNode(-4);
        p1 = p1.next;
        p1.next = new ListNode(-5);
        p1 = p1.next;
        p1.next = temp;

        p2.next = new ListNode(40);
        p2 = p2.next;
        p2.next = new ListNode(50);
        p2 = p2.next;
        p2.next = new ListNode(60);
        p2 = p2.next;
        p2.next = temp;


        ListNode returnListNode = DoublePointerInLinkedList.getIntersectionNode(l1, l2);
        ListNode p = returnListNode;
        System.out.println("第一个交点的值:" + p.val);
    }
}

到了这里,关于链表-双指针-虚拟节点-力扣的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【2023】华为OD机试真题全语言-题目0233-单向链表中间节点

    求单向链表中间的节点值,如果奇数个节点取中间,偶数个取偏右边的那个值。 第一行 链表头节点地址 后续输入的节点数 n n n 后续输入每行表示一个节点,格式 节点地址 节点值 下一个节点地址( -1 表示空指针) 输入保证链表不会出现环,并且可能存在一些节点不属于链表

    2024年02月05日
    浏览(39)
  • 【免费题库】华为OD机试 - 虚拟理财游戏(Java & JS & Python & C & C++)

    哈喽,本题库完全免费,收费是为了防止被爬,大家订阅专栏后可以私信联系退款。感谢支持 在一款虚拟游戏中生活,你必须进行投资以增强在虚拟游戏中的资产以免被淘汰出局。 现有一家Bank,它提供有若干理财产品 m 个,风险及投资回报不同,你有 N(元)进行投资,能

    2024年04月12日
    浏览(54)
  • 【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表

      目录 1、题目介绍 2、解题思路 2.1、暴力破解法 2.2、快慢指针反转链表   原题链接:  234. 回文链表 - 力扣(LeetCode) 示例 1: 输入: head = [1,2,2,1] 输出: true  示例 2: 输入: head = [1,2] 输出: false  提示:  链表中节点数目在范围[1, 10^5] 内 0 = Node.val = 9 进阶: 你能否用

    2024年02月08日
    浏览(45)
  • 力扣-复制带随机指针的链表

    给你一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random  ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的  深拷贝 。 深拷贝应该正好由  n  个  全新  节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的  next  指针和

    2024年02月11日
    浏览(46)
  • 【华为od机试 2023】 什么是华为od 机试题库清单以及说明

    本题库包含 2022 Q4的题目。 文章标题的 100% 代表 代码的AC率为100% 分值 文章 考点 100 【华为OD机试 2023最新 】 工单调度策略(C++ 100%) 优先队列 100 【华为OD机试 2023最新 】 最多几个直角三角形(C++ 100%) 回溯算法 100 【华为OD机试 2023最新 】 最优资源分配(C++) 逻辑分析

    2023年04月09日
    浏览(90)
  • 环形链表 II(力扣142)(快慢指针)

    142.环形链表—力扣 给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到

    2023年04月25日
    浏览(40)
  • 【华为OD题库-083】玩牌高手-Java

    给定一个长度为n的整型数组,表示一个选手在n轮内可选择的牌面分数。选手基于规则选牌,请计算所有轮结束后其可以获得的最高总分数。 选择规则如下: 1.在每轮里选手可以选择获取该轮牌面,则其总分数加上该轮牌面分数,为其新的总分数。 2.选手也可不选择本轮牌面直

    2024年02月04日
    浏览(47)
  • LC-链表的中间节点(双指针)

    链接:https://leetcode.cn/problems/middle-of-the-linked-list/description/ 描述:给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 输入:head = [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个中间结点,值为 3 。 输入:head = [1,2,3,4,5,6

    2024年02月12日
    浏览(46)
  • 力扣:117. 填充每个节点的下一个右侧节点指针 II(Python3)

    给定一个二叉树: 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为  NULL  。 初始状态下,所有 next 指针都被设置为  NULL  。 来源:力扣(LeetCode) 链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 示

    2024年02月07日
    浏览(45)
  • 力扣hot100 环形链表 快慢指针 哈希 数学公式

    Problem: 142. 环形链表 II 👨‍🏫 参考题解 ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( 1 ) O(1) O ( 1 )

    2024年01月23日
    浏览(70)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包