Problema
Escriba un programa para encontrar el nodo en el que comienza la intersección de dos listas enlazadas individualmente.
Por ejemplo, las siguientes dos listas enlazadas:
A: a1 -> a2
->
c1 -> c2 -> c3
->
B: b1 -> b2 -> b3
comienzan a cruzarse en el nodo c1.
Solución Java
Primero calcule la longitud de dos listas y encuentre la diferencia. Luego, comience desde la lista más larga en el desplazamiento diferencial, recorra 2 listas y encuentre el nodo.
/** * 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 len1 = 0; int len2 = 0; ListNode p1=headA, p2=headB; if (p1 == null || p2 == null) return null; while(p1 != null){ len1++; p1 = p1.next; } while(p2 !=null){ len2++; p2 = p2.next; } int diff = 0; p1=headA; p2=headB; if(len1 > len2){ diff = len1-len2; int i=0; while(i<diff){ p1 = p1.next; i++; } }else{ diff = len2-len1; int i=0; while(i<diff){ p2 = p2.next; i++; } } while(p1 != null && p2 != null){ if(p1.val == p2.val){ return p1; } p1 = p1.next; p2 = p2.next; } return null; } } |
