Schnittpunkt zweier LinkedLists

Problem

Brute-Force-Ansatz:

Zeitliche Komplexität: O(N+M), wobei N und M die Länge von zwei angegebenen LinkedLists sind.

Intuition

Ermitteln Sie die Länge beider Knoten und ermitteln Sie den Längenunterschied
Gehen Sie in der längsten Liste um den Längenunterschied beider Listen voran, dadurch beginnen beide Listen mit der gleichen Länge.
Rückkehr, wenn dieselben Knoten angetroffen werden.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = findLength(headA);
        int lenB = findLength(headB);
        ListNode A = headA;
        ListNode B = headB;

        int diff = Math.abs(lenA-lenB);
        if(lenA > lenB){
            A = travelAhead(A,diff);
        }
        else B = travelAhead(B,diff);

        return findIntegersection(A,B);
    }
    public ListNode findIntegersection(ListNode a, ListNode b){
        while(a!=null && b!=null){
            if(a.equals(b)) return a;
            a= a.next;
            b= b.next;
        }
        return null;
    }
    public ListNode travelAhead(ListNode head, int diff){
        while(diff-->0){
            head = head.next;
        }
        return head;
    }
    public int findLength(ListNode head){
        int count = 0;
        while(head!=null){
            head = head.next;
            count++;
        }
        return count;
    }
}

Das obige ist der detaillierte Inhalt vonSchnittpunkt zweier LinkedLists. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!