你的位置:首页 > Java教程

[Java教程][LeetCode] Intersection of Two Linked Lists


Write a program to find the node at which the intersection of two singly linked lists begins.

 

For example, the following two linked lists: 

A:     a1 → a2          ↘           c1 → c2 → c3          ↗      B:   b1 → b2 → b3

begin to intersect at node c1.

 

Notes:

    • If the two linked lists have no intersection at all, return null.
    • The linked lists must retain their original structure after the function returns. 
    • You may assume there are no cycles anywhere in the entire linked structure.
    • Your code should preferably run in O(n) time and use only O(1) memory.

     这道题还是先要搞懂题目问的啥。这里的intersection linked list通过看例子我们可以看出,其length可以不一样,但是从intersect的部分开始到结束长度是一样的,所以说多余的只会是前面的几个值,而且一定有较长length的那个linked list多余出来的那一段的值。

     所以我们首先计算两个list的length,把较长的那个的多余的那部分的值给waive掉。这样两条同样长的list就非常好找intersect的地方了。

     代码如下。~

/** * 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 lengtha=0;    int lengthb=0;    ListNode curr1=headA;    ListNode curr2=headB;    while(curr1!=null){      lengtha++;      curr1=curr1.next;    }    while(curr2!=null){      lengthb++;      curr2=curr2.next;    }    curr1=headA;    curr2=headB;    if(lengtha>lengthb){      for(int i=0;i<lengtha-lengthb;i++){        curr1=curr1.next;      }    }else{      for(int i=0;i<lengthb-lengtha;i++){      curr2=curr2.next;      }    }    while(curr1!=curr2){      curr1=curr1.next;      curr2=curr2.next;    }    return curr1;  }}