Intersection of Two LinkedLists

Leave a comment

November 6, 2016 by oneOokay

我觉得目前我貌似到了一种:哎我能想到可以这么做,但是还写不出来的状态。囧。

有个Intersection of Two Arrays

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.

我能想到的:

首先while loop循环两个linkedlist: p1 & p2. 若其中一个假设p1到达末尾了,把p1放到linkedlist2的头上,继续进行循环。当p2也到达末尾时,把p2放到linkedlist1上继续循环。此时p1,p2是在与中点相同距离的地方。此时开始判断p1是否等于p2。然后没有写成功。

看了眼最佳答案,跟我类似,但是妙的是用p1 是否等于p2来作为while loop的条件,超短的代码:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null){
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2){
p1 = p1 == null ? headB : p1.next; //这两行很妙啊
p2 = p2 == null ? headA : p2.next;
}
return p1; //如果两者没有intersection的话,那么当loop结束的时候p1 == p2 == null
}

一般的解法:

  1. 求得linkedlist1 和 linkedlist2的长度
  2. 把p1 & p2移到与终点距离相同的位置 (可以看一下代码)
  3. loop进行判断
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 if (headA == null || headB == null){
 return null;
 }
 
 int lengthA = getLength(headA);
 int lengthB = getLength(headB);
 
 ListNode p1 = headA;
 ListNode p2 = headB;
 
 while (lengthA > lengthB){
 p1 = p1.next;
 lengthA --;
 }
 
 while (lengthB > lengthA){
 p2 = p2.next;
 lengthB --;
 }
 
 while(p1 != null && p2 != null){
 if (p1 == p2){
 return p1;
 }
 p1 = p1.next;
 p2 = p2.next;
 }
 
 return null;
 }
 
 private int getLength(ListNode head){
 if (head == null){
 return 0;
 }
 
 int length = 0;
 while (head != null){
 head = head.next;
 length ++;
 }
 
 return length;
 }

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: