leetcode/IntersectionofTwoLinkedLists.cpp at master · witwolf/leetcode · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
//
//  IntersectionofTwoLinkedLists.cpp
//  leetcode
//
//  Created by witwolf on 5/4/15.
//  Copyright (c) 2015 witwolf. All rights reserved.
//

#include <stdio.h>


/**
 * Definition for singly-linked list.
 */

struct ListNode {
    int val;
    struct ListNode *next;
};

int len(struct ListNode *root){
    int length = 0;
    while(root){
        length++;
        root = root->next;
    }
    return length;
}

struct ListNode* forward(struct ListNode * node,int stride){
    while(stride -- ){
        node = node->next;
    }
    return node;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int lenA = len(headA);
    int lenB = len(headB);
    if(lenA > lenB){
        headA = forward(headA, lenA - lenB);
    }else if(lenB > lenA){
        headB = forward(headB, lenB - lenA);
    }
    while (headA && headB) {
        if(headA == headB){
            return  headA;
        }
        headA = headA->next;
        headB = headB->next;
    }

    return headA;
}