Java에서 간단하고 최적의 방법으로 두 개의 단일 연결 목록의 교차점을 찾는 방법

간단하고 최적의 방법으로 두 개의 단일 연결 목록의 교차점을 찾으려면 다음 접근 방식을 사용할 수 있습니다. 핵심 아이디어는 긴 목록의 시작점을 조정하여 두 연결 목록의 끝을 정렬한 다음 두 목록을 동시에 탐색하여 교차점을 찾는 것입니다.

단계:

1. 길이 계산: 먼저 두 연결 목록의 길이를 계산합니다.
2. 시작 포인터 정렬: 한 목록이 다른 목록보다 긴 경우 해당 포인터를 이동하여 두 목록의 길이를 맞춥니다.
3. 교차점 찾기: 두 목록을 동시에 탐색합니다. 그들이 만나는 첫 번째 노드가 교차점입니다.

자바 구현:

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 )은 두 연결 목록의 길이입니다. 목록은 최대 2번 순회됩니다.
• 공간 복잡도: ( O(1) ), 몇 개의 추가 포인터만 사용되기 때문입니다.

이 방법은 간단하고 최적이므로 효율적인 방식으로 두 개의 단일 연결 목록의 교차점을 찾을 수 있습니다.

위 내용은 Java에서 간단하고 최적의 방법으로 두 개의 단일 연결 목록의 교차점을 찾는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!