weixin_38393017 2017-09-15 11:52 采纳率: 0%
浏览 357

关于如何用java创建一条相交链表问题

问题是写出能求出这条链表是否相交和找出第一个相交节点的函数,但是首先创建一条相交链表才能
或者怎么传进来一条链表?

  • 写回答

1条回答 默认 最新

  • 憧憬blog 2023-06-27 09:47
    关注

    要创建一条相交链表,可以先创建两条单独的链表,然后将它们的尾节点相连,形成一条相交链表。以下是一个示例代码:

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    
    public class IntersectionLinkedList {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // 先找到两条链表的尾节点
            ListNode tailA = headA;
            while (tailA != null && tailA.next != null) {
                tailA = tailA.next;
            }
            ListNode tailB = headB;
            while (tailB != null && tailB.next != null) {
                tailB = tailB.next;
            }
            // 如果两条链表的尾节点不同,说明不相交,返回null
            if (tailA != tailB) {
                return null;
            }
            // 将两条链表相连,形成一条相交链表
            tailA.next = headB;
            // 找到相交节点
            ListNode intersectionNode = getIntersection(headA);
            // 恢复链表
            tailA.next = null;
            return intersectionNode;
        }
        
        private ListNode getIntersection(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    ListNode ptr = head;
                    while (ptr != slow) {
                        ptr = ptr.next;
                        slow = slow.next;
                    }
                    return ptr;
                }
            }
            return null;
        }
    }
    

    该代码中的 ListNode 类表示链表节点,包含一个整数值和一个指向下一个节点的指针。 IntersectionLinkedList 类包含一个 getIntersectionNode 方法,用于判断两条链表是否相交,并返回第一个相交节点。该方法先找到两条链表的尾节点,如果不同则说明不相交,直接返回 null。如果相同,则将两条链表相连形成一条相交链表,然后调用另一个方法 getIntersection 来找到相交节点。该方法使用快慢指针法,先让快指针走两步,慢指针走一步,直到它们相遇,然后从头开始遍历链表,直到快指针和慢指针相遇,此时的节点就是相交节点。

    创建链表可以定义一个方法,例如:

    public ListNode createLinkedList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        ListNode head = new ListNode(arr[0]);
        ListNode tail = head;
        for (int i = 1; i < arr.length; i++) {
            ListNode node = new ListNode(arr[i]);
            tail.next = node;
            tail = node;
        }
        return head;
    }
    

    该方法接受一个整型数组,返回一个链表的头节点。例如,要创建一个值为 1 -> 2 -> 3 的链表,可以这样调用:

    int[] arr = {1, 2, 3};
    ListNode head = createLinkedList(arr);
    
    评论

报告相同问题?

悬赏问题

  • ¥15 vue3项目使用router构建多个页面,页面跳转时不刷新就显示空白
  • ¥20 针对计算后数据做一致性检验可以用Bland Altman法吗
  • ¥15 win32如何自绘编辑框的背景图片(语言-c++|操作系统-windows)
  • ¥15 微信夜间被转走了1w对,当天手机剪切板里就出现了这个乱码,有铁子可以看看是啥吗可以
  • ¥50 跑通github上的代码 深度学习 pytorch
  • ¥50 求写,批处理调用分区助手分区脚本
  • ¥15 求购HI3519AV100开发板
  • ¥15 请问1553 RT怎么测试,没有BC有方法吗
  • ¥15 wamp3.3.5安装完成后图标正常显示绿色,鼠标左右键点击图标均无反应。求解决方法。
  • ¥15 鼠标点击的这条记录了什么?