Leetcode-160Intersection of Two

160. 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.

题解：

本题要求两个链表的第一个公共节点，从题目样例的图上，可以发现，我们只需要将长的链表B多出的部分去掉，让A,B链表的头结点a1,b2对齐，一起向右移动，就可以得到第一个公共节点c1，下面给出C++和Python的相应代码：
My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

int GetLenNode(ListNode *head) {
    int len = 0;
    while(head) {
        head = head->next;
        len += 1;
    }
    return len;
}

ListNode *ChangeLongNode(int long_len, int short_len, ListNode *head) {
    int del_len = long_len - short_len;
    while(del_len) {
        head = head->next;
        del_len -= 1;
    }
    return head;
}

class Solution {
public:
    ListNode *FindFirstCommonNode(ListNode *headA, ListNode *headB) {
        int lenA = GetLenNode(headA);
        int lenB = GetLenNode(headB);
        if(lenA > lenB) {
            headA = ChangeLongNode(lenA, lenB, headA);
        }
        else {
            headB = ChangeLongNode(lenB, lenA, headB);
        }
        while(headA && headB) {
            if(headA == headB) {
                return headA;
            }
            else {
                headA = headA->next;
                headB = headB->next;
            }
        }
        return NULL;
    }
};

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    ListNode f(6);
    ListNode g(7);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    g.next = &f;
    f.next = &e;
    Solution s;
    ListNode *result = s.FindFirstCommonNode(&a, &g);
    printf("%d\n", result->val);
    return 0;
}

结果展示：

5

Process returned 0 (0x0)   execution time : 0.090 s
Press any key to continue.

My Solution(Python3):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getLenOfNode(self, headA, headB):
        len_A = len_B = 0
        while headA:
            len_A += 1
            headA = headA.next
        while headB:
            len_B += 1
            headB = headB.next
        return len_A, len_B
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        len_A, len_B = getLenOfNode(self, headA, headB)
        if len_A > len_B:
            num = len_A - len_B
            while num:
                headA = headA.next
                num -= 1
        if len_A < len_B:
            num = len_B - len_A
            while num:
                headB = headB.next
                num -= 1
        while headA:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        return None

Reference:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA and headB:
            A, B = headA, headB
            while A!=B:
                A = A.next if A else headB
                B = B.next if B else headA
            return A