如何在java中以简单且最佳的方式找到两个单链表的交集

要以简单且最佳的方式找到两个单链表的交集，您可以使用以下方法。关键思想是通过调整较长链表的起点来对齐两个链表的末端，然后同时遍历两个链表以找到交点。

步骤：

1. 计算长度：首先计算两个链表的长度。
2. 对齐起始指针：如果一个列表比另一个列表长，则前进其指针以对齐两个列表的长度。
3. 查找交集：同时遍历两个列表。它们相遇的第一个节点是交点。

Java实现：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to get the intersection node of two linked lists
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // Calculate the lengths of both linked lists
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);

        // Align the start of both lists
        while (lengthA > lengthB) {
            headA = headA.next;
            lengthA--;
        }

        while (lengthB > lengthA) {
            headB = headB.next;
            lengthB--;
        }

        // Traverse both lists together to find the intersection
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;  // or headB, they are the same at intersection point
    }

    // Utility function to calculate the length of a linked list
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create two linked lists
        // List A: 1 -> 3 -> 5 -> 7 -> 9 -> 11
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(3);
        headA.next.next = new ListNode(5);
        headA.next.next.next = new ListNode(7);
        headA.next.next.next.next = new ListNode(9);
        headA.next.next.next.next.next = new ListNode(11);

        // List B: 2 -> 4 -> 9 -> 11
        ListNode headB = new ListNode(2);
        headB.next = new ListNode(4);
        headB.next.next = headA.next.next.next.next;  // 9
        headB.next.next.next = headA.next.next.next.next.next;  // 11

        System.out.println("List A:");
        list.printList(headA);

        System.out.println("List B:");
        list.printList(headB);

        // Find intersection
        ListNode intersection = list.getIntersectionNode(headA, headB);

        if (intersection != null) {
            System.out.println("Intersection at node with value: " + intersection.val);
        } else {
            System.out.println("No intersection.");
        }
    }
}

解释：

1. ListNode 类:

   • 用值（val）和指向下一个节点（next）的指针表示链表中的每个节点。

2. getIntersectionNode 方法:

   • 计算长度：使用 getLength 方法计算两个链表的长度。
   • 对齐起始指针：如果列表的长度不同，则较长列表的指针会前移以与较短列表的指针对齐。
   • 一起遍历：两个指针同时移动。它们匹配的第一个节点是交集节点。

3. getLength 方法:

   • 计算链表长度的辅助方法。

4. printList 方法:

   • 打印链表节点的实用函数。

5. 主要方法:

   • 创建两个链表：例如1 -> 3-> 5-> 7-> 9-> 11和2-> 4-> 9-> 11，交叉点从节点 9 开始。
   • 查找并打印交点：程序将输出 9 作为交点。

复杂：

• 时间复杂度： ( O(m + n) )，其中 ( m ) 和 ( n ) 是两个链表的长度。列表最多遍历两次。
• 空间复杂度：( O(1) )，因为只使用了一些额外的指针。

此方法简单且最优，确保您高效地找到两个单链表的交点。

以上是如何在java中以简单且最佳的方式找到两个单链表的交集的详细内容。更多信息请关注PHP中文网其他相关文章！