算法通关村第一关------链表经典问题之寻找第一个公共子结点

这篇具有很好参考价值的文章主要介绍了算法通关村第一关------链表经典问题之寻找第一个公共子结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一共有四种方法:

  1. 哈希和集合
  2. 拼接两个字符串
  3. 同步相消

1、哈希和集合法:

        将一个链表存入Map(或者集合)中,然后遍历第二个链表,在遍历的同时,检查在Hash(或者集合)中是否包含此节点。

//哈希法
    public static ListNode findFirstCommonNodeByMap(ListNode pHead1, ListNode pHead2) {
        //判断两个链表的头结点是否为空,有一个为空,则无法寻找第一个公共节点
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        //创建一个Hash对象,用来存储链表元素
        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        //遍历第二个链表,遍历的同时,检测Hash中是否包含此结点
        while (current2 != null) {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }
        return null;
    }

//集合法、与哈希法思想相似
    public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            if (set.contains(headB))
                return headB;
            headB = headB.next;
        }
        return null;
    }

 2、栈方法:

        主要思想:栈是后进先出原则,stack.peek()方法每次比较栈顶元素,也就是链表最后一位,由于求第一个公共元素,那么,对于这两个链表来说,第一个公共结点到两个链表的最后一个结点距离是一致的,且值一一对应相等(举例:a链表,1->2->3->4->5,b链表,11->22->4->5。这俩链表第一个刚刚结点“4”,距离最后一位元素距离都是1,且a的4与b的4对应,a的5与b的5对应)。若第一次判断栈顶元素就不相等,那么这俩链表一定没有公共结点。

        操作步骤:将两个链表分别压入两个栈中,先定义一个空的preNode对象,目的是:最终用来返回第一个公共子节点。先判断两个栈的大小都大于0,确保有值进行比较,然后依次获取两个栈的栈顶元素(stackA.peek() == stackB.peek()),如果相等将此栈顶元素弹栈,并且用preNode结点接受,然后继续比较两个栈顶元素是否相等,直到不等情况出现,那么此时preNode结点就是我们要寻找的第一个公共结点。

public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {
        Stack<ListNode> stackA = new Stack();
        Stack<ListNode> stackB = new Stack();
        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }

        ListNode preNode = null;
        while (stackB.size() > 0 && stackA.size() > 0) {
            //比较栈顶元素是否相等
            if (stackA.peek() == stackB.peek()) {
                //若相等,将栈顶元素弹栈,并且用preNode结点接收
                preNode = stackA.pop();
                stackB.pop();   //第二个链表的栈,栈顶元素同样弹栈
            } else {
                break;  //当判断两个栈顶元素首次不相等时,说明上一次弹栈的元素就是第一个公共结点
            }
        }
        return preNode;
    }

3、拼接字符串

        主要思想:两个链表第一个公共结点起,到最后一个结点的值都相互对应。不放将两个链表以第一个公共结点为分界点彼此分为两部分,a链表的右半部分跟b链表的右半部分是一模一样的,所以不论是a接到b的后边,还是b接到a的后边,这两个字符串的最后一段一定是一模一样的。

示例图:

算法通关村第一关------链表经典问题之寻找第一个公共子结点,链表,数据结构

 

public static ListNode findFirstCommonNodeByCombine(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            if (p1 != p2) {//当p1==p2时,就意味着遍历到了 示例图 中的第四部分(公共元素部分)
                //a链表遍历完后,将b链表拼接在a链表的后边
                if (p1 == null) {
                    p1 = pHead2;
                }
                //同理,b链表遍历完后,将a链表
                if (p2 == null) {
                    p2 = pHead1;
                }
            }
        }
        return p1;
    }

4、同步相消

        名词解释:同步相消就是,链表长的先消除几步,使得两个链表长度相等。然后两个链表同步遍历,结点第一次一致的时候,就是第一个公共结点。

        

public static ListNode findFirstCommonNodeBySub(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        int l1 = 0, l2 = 0;
        //遍历链表得到链表的长度
        while (current1 != null) {
            current1 = current1.next;
            l1++;
        }
        while (current2 != null) {
            current2 = current2.next;
            l2++;
        }
        //重新将两个指针分别指向链表的头结点
        current1 = pHead1;
        current2 = pHead2;

        int sub = l1 > l2 ? l1 - l2 : l2 - l1;
        if (l1 > l2) {
            int a = 0;
            while (a < sub) {
                current1 = current1.next;
                a++;
            }
        }
        if (l1 < l2) {
            int a = 0;
            while (a < sub) {
                current2 = current2.next;
                a++;
            }
        }
        //消除步差之后,同步遍历,然后看结点是否一致。首次一致,那么这个结点就是第一个公共结点
        while (current2 != current1) {
            current2 = current2.next;
            current1 = current1.next;
        }
        return current1;
    }

附录

        完成上述操作所需的初始化代码(例如链表的构造及初始化、switch语句,方便使用不同的方法来实现)文章来源地址https://www.toymoban.com/news/detail-660456.html

public class FindFirstCommonNode {
    public static void main(String[] args) {
        ListNode[] heads = initLinkedList();
        //la 为 1 2 3 4 5
        //lb 为 11 22 4 5
        ListNode la = heads[0];
        ListNode lb = heads[1];

        int testMethod = 5;
        ListNode node = new ListNode(0);
        switch (testMethod) {
            case 1: //方法1:通过Hash辅助查找
                node = findFirstCommonNodeByMap(la, lb);
                break;
            case 2: //方法2:通过集合辅助查找
                node = findFirstCommonNodeBySet(la, lb);
                break;
            case 3://方法3:通过栈辅助查找
                node = findFirstCommonNodeByStack(la, lb);
                break;
            case 4://方法4:通过拼接辅助查找
                node = findFirstCommonNodeByCombine(la, lb);
                break;
            case 5://方法5:通过差辅助查找
                node = findFirstCommonNodeBySub(la, lb);
                break;
        }

        System.out.println("公共结点为:" + node.val);

    }

    private static ListNode[] initLinkedList() {
        ListNode[] heads = new ListNode[2];
//        构造第一个链表交点之前的元素 1 ->2-> 3
        heads[0] = new ListNode(1);
        ListNode current1 = heads[0];
        current1.next = new ListNode(2);
        current1 = current1.next;
        current1.next = new ListNode(3);
        current1 = current1.next;
//        11->22
//        构造第二个链表交点之前的元素
        heads[1] = new ListNode(11);
        ListNode current2 = heads[1];
        current2.next = new ListNode(22);
        current2 = current2.next;
//        构造公共交点以及之后的元素

        ListNode node4 = new ListNode(4);
        current1.next = node4;
        current2.next = node4;
        ListNode node5 = new ListNode(5);
        node4.next = node5;


        ListNode node6 = new ListNode(6);
        node5.next = node6;

        return heads;
    }

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

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}

到了这里,关于算法通关村第一关------链表经典问题之寻找第一个公共子结点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法通关村第一关——链表经典问题之双指针笔记

    基本结构 1.寻找中间结点 2.寻找倒数第k个元素 3.旋转链表

    2024年02月14日
    浏览(38)
  • 算法通关村第一关——链表经典问题之双指针专题笔记

    我一直觉得双指针是一个非常好用的方法,在链表中可以使用,在数组中依然可以,很灵活。 1. 寻找中间结点         用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步, fast 一次走两步。那么当 fast 到达链表的末尾时,slow 必然位于中间。 2. 寻找倒数第K个元素 在这

    2024年02月15日
    浏览(40)
  • 《算法通关村第一关——链表青铜挑战笔记》

    链表中每个结点内部的“生态环境”。 数据域存储元素的值,指针域存放指针。 示例: c语言构造链表 可分为三步 1.创建头指针。 2.创建头结点,使头指针指向头结点。 3.循环创建结点,并使前一个结点指向当前结点。 1.)创建结点。 2.)使前一个结点指向当前结点。 3.)

    2024年02月15日
    浏览(38)
  • 算法通关村第一关———链表青铜挑战笔记

    通过类来构建节点,用next指针将节点连起来。 会有插入位置的范围问题,不能超出链表范围 会有删除位置的范围问题 构造双向链表 插入和删除都有三种情况,头中尾  

    2024年02月15日
    浏览(42)
  • 算法通关村第一关--链表青铜挑战笔记

    开始时间:2023年7月16日20:45:26 什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是hea

    2024年02月17日
    浏览(42)
  • 算法通关村第一关 | 链表青铜挑战笔记

    一、 什么是链表? 链表是一种比较简单、很常见的数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 二、链表的特点 链表是一种比较简单、很常见的数据结构,是线性表(List)的一种,是一种物理存

    2024年02月14日
    浏览(36)
  • 算法通关村第一关-链表青铜挑战笔记

    平时我们一般都是用数组,每个数组都会有一个相对应的索引,这样就使得数组能够方便的调用出对应索引得到需要的数据,但是这也造成了一个问题,那就是不好在数组中插入或者删除一个数据,例如 int arr[]={1,2,4,5}如果我想在数组中的2和4中添加一个数据3 那么我们首先就

    2024年02月15日
    浏览(41)
  • 算法通关村第一关——链表青铜挑战笔记

    链表的基本单元就是 节点 ,也就是说链表是由一个一个节点构成的。 而对于节点来说,里面至少会包含一个 指针 和一个 数据元素 ,也就是如下图所示: 其中数据域用来存放数据元素,指针域用来存放指向下一个节点的指针,这样一个一个连接起来的就是链表。如下图所

    2024年02月16日
    浏览(40)
  • 编程导航算法通关村第一关|青铜|链表基础

    JVM有栈区和堆区 栈区:存引用,就是指向实际对象的地址。。 堆区:存的是创建的对象。 定义 规范的链表定义 LeetCode算法题中常用 遍历 插入 删除 结点 结构遍历 插入 从头插入 从尾插入 从某个值为key的节点后面插入 删除 删除头结点 删除尾结点 按值删除

    2024年02月15日
    浏览(40)
  • 算法通关村第一关——链表青铜挑战笔记(单链表)

    在LeeCode中一般这样创建链表 要注意创建一个变量来遍历,不要把head丢掉了 count position - 1可以方便操作,还能防止下标越界(cur为null)

    2024年02月15日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包