Home > Java > javaTutorial > body text

Intersection of two LinkedLists

PHPz
Release: 2024-07-21 08:54:58
Original
829 people have browsed it

Intersection of two LinkedLists

Problem

Brute force approach:

Time complexity: O(N+M) where N and M are length of two LinkedLists given.

Intuition

Find length of both the nodes and get the length difference
Travel ahead in the longest list by length difference of both the lists, by this both the lists will start from the same length.
return when same nodes are encountered.

/**
 * 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;
    }
}
Copy after login

The above is the detailed content of Intersection of two LinkedLists. For more information, please follow other related articles on the PHP Chinese website!

source:dev.to
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template