2016年2月14日 星期日

LEET code -- 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.


我先想到的是用stack  來記住list
再慢慢POP出來  看有沒有一樣
如果兩個Stack一開始POP就不一樣  那代表沒有重複
如果是一段重複 突然出現不一樣  那代表最後出現重複的是答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL ||headB==NULL)return NULL;
    int maxsize=128;
    struct ListNode** Astack=malloc(sizeof(struct ListNode*)*maxsize);
    struct ListNose** Bstack=malloc(sizeof(struct ListNode*)*maxsize);
    int Asize=0,Bsize=0;
    struct ListNode *tempA=headA, *tempB=headB;
    while(tempA!=NULL || tempB!=NULL){
        if(tempA==tempB)return tempA;
        if(tempA){
            Astack[Asize++]=tempA;
            tempA=tempA->next;
        }
        if(tempB){
            Bstack[Bsize++]=tempB;
            tempB=tempB->next;
        }
        if(Asize >= maxsize-10 || Bsize>= maxsize-10){
            maxsize*=2;
            Astack=realloc(Astack,sizeof(struct ListNode*)*maxsize);
            Bstack=realloc(Bstack,sizeof(struct ListNode*)*maxsize);
        }
    }
    struct ListNode* pre=NULL;
    tempA=NULL;
    while(Asize>0 && Bsize>0){
        tempA=Astack[--Asize];
        tempB=Bstack[--Bsize];
        printf("%d %d ",tempA->val,tempB->val);
        if(tempA->val!=tempB->val)return pre;
        pre=tempA;
    }
    return pre;
    
}
-----------------
超天才解法
https://leetcode.com/discuss/66203/java-solution-without-knowing-the-difference-in-len


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


A的長度=5


B的長度=6


假設今天有兩個指標CA  CB分別從A跟B的頭出發


一起前進，非常合理的A會先走到盡頭


此時CA走到C3  CB走道c2




這時候CA因為走到盡頭了   改從B的頭從頭走過


所以下一點變成CA在b1    CB在C3


CB因為也走到盡頭了  改走a1


此時會發現CA在b2   CB在a1  會同時並行!!!




原因  假設A的長度是T   B是Y


那假設A跟B的長度一開始就是T<=Y


所以兩者長度相差就是D=Y-T


當A的指標走到底了B還會剩下D的步數才會走完


此時把A指標換到B的頭  會造成B跟A差距T


當B也走完的時候  換成A的頭




這樣的差距D剛好會被同時追上  造成兩個指標平行


  










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL ||headB==NULL)return NULL;
    
    struct ListNode *curA = headA,*curB=headB;
    
    while(curA && curB){
        if(curA == curB)return curA;
        curA=curA->next;
        curB=curB->next;
        if(curA==NULL && curB==NULL)return NULL;
        if(curA==NULL)curA=headB;
        if(curB==NULL)curB=headA;
        
    }
    return curA;
}

















張貼者：



於





















標籤：


















沒有留言:















張貼留言


















        

      









訂閱：
張貼留言 (Atom)