online advertising

## Wednesday, April 1, 2015

### LeetCode OJ - Intersection of Two Linked Lists

Problem:

Please find the problem here.

Solutoin:

If the lists are of the same length - it is an easy problem to solve.

So let's make it so! By using a separate scan, we know the lengths of the lists, just advance the pointer of the longer list so that they aligns, then we can solve this easily.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/intersection-of-two-linked-lists/

#include "LEET_INTERSECTION_OF_TWO_LINKED_LISTS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

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

class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
int a_length = 0;
int b_length = 0;
ListNode* a_cursor = headA;
ListNode* b_cursor = headB;

// Step 1: Determine the lengths
while (a_cursor != NULL)
{
a_cursor = a_cursor->next;
a_length++;
}
while (b_cursor != NULL)
{
b_cursor = b_cursor->next;
b_length++;
}

// Step 2: Align the lists
int a_remaining_length = a_length;
int b_remaining_length = b_length;
a_cursor = headA;
b_cursor = headB;

while (a_remaining_length > b_remaining_length)
{
a_cursor = a_cursor->next;
a_remaining_length--;
}
while (a_remaining_length < b_remaining_length)
{
b_cursor = b_cursor->next;
b_remaining_length--;
}

// Step 3: Determine the intersection
while (a_cursor != b_cursor)
{
a_cursor = a_cursor->next;
b_cursor = b_cursor->next;
}

return a_cursor;
}
};
};

using namespace _LEET_INTERSECTION_OF_TWO_LINKED_LISTS;

int LEET_INTERSECTION_OF_TWO_LINKED_LISTS()
{
ListNode a1(1);
ListNode a2(1);
ListNode b1(1);
ListNode b2(1);
ListNode b3(1);
ListNode c1(1);
ListNode c2(1);
ListNode c3(1);

a1.next = &a2; a2.next = &c1;
b1.next = &b2; b2.next = &b3; b3.next = &c1;
c1.next = &c2; c2.next = &c3; c3.next = NULL;

Solution solution;
cout << (solution.getIntersectionNode(&a1, &b1) == &c1) << endl;

return 0;
}