LeetCode160. 相交链表

Seawolf

1. Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
   
2. Output: Reference of the node with value = 8
   
3. Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

复制代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) {
   
7. *         val = x;
   
8. *         next = null;
   
9. *     }
   
10. * }
    
11. */
    
12. public class Solution {
    
13.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
14.         
    
15.         ListNode pa = headA;
    
16.         ListNode pb = headB;
    
17.         
    
18.         int lengthA = 0;
    
19.         int lengthB = 0;
    
20.         
    
21.         while(pa != null){
    
22.             
    
23.             lengthA ++;
    
24.             pa = pa.next;
    
25.         }
    
26.         
    
27.         while(pb != null){
    
28.             
    
29.             lengthB ++;
    
30.             pb = pb.next;
    
31.         }
    
32.         
    
33.         int dif = Math.abs(lengthA - lengthB);
    
34.         
    
35.         while(dif != 0){
    
36.             
    
37.             if(lengthA >= lengthB){
    
38.                
    
39.                 headA = headA.next;
    
40.             }
    
41.             else{
    
42.                
    
43.                 headB = headB.next;
    
44.             }
    
45.             
    
46.             dif--;
    
47.         }
    
48.         
    
49.         while(headA != null && headB != null){
    
50.             
    
51.             if(headA == headB){
    
52.                
    
53.                 return headA;
    
54.             }
    
55.             
    
56.             headA = headA.next;
    
57.             headB = headB.next;
    
58.             
    
59.         }
    
60.         
    
61.         return null;
    
62.         
    
63.     }
    
64. }

复制代码