By

文章目录

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

1
2
3
4
5
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

Method 1(Simply use two loops)
Use 2 nested for loops. Outer loop will be for each node of the 1st list and inner loop will be for 2nd list. In the inner loop, check if any of nodes of 2nd list is same as the current node of first linked list. Time complexity of this method will be O(mn) where m and n are the number of nodes in two lists.

Method 2 (Mark Visited Nodes)
This solution requires modifications to basic linked list data structure. Have a visited flag with each node. Traverse the first linked list and keep marking visited nodes. Now traverse second linked list, If you see a visited node again then there is an intersection point, return the intersecting node. This solution works in O(m+n) but requires additional information with each node. A variation of this solution that doesn’t require modification to basic data structure can be implemented using hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in hash then return the intersecting node.

Method 3(Using difference of node counts)
1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)

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
55
56
57
58
59
60
61
62
63
64
65
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL || headB==NULL)
            return NULL;
        ListNode* tempNode = headA;
        ListNode* tNode = NULL;
        int tNum = 0;
        int count1 = 0;
        int count2 = 0;
        while(tempNode!=NULL)
        {
            count1++;
            tempNode = tempNode->next;
        }
        tempNode = headB;
        while(tempNode!=NULL)
        {
            count2++;
            tempNode = tempNode->next;
        }
        if(count1>=count2)
        {
            tempNode = headA;
            tNum = count1-count2;
            tNode = headB;
        }
        else
        {
            tempNode = headB;
            tNum = count2-count1;
            tNode = headA;
        }
        for(int i=0;i<tNum; i++)
        {
            tempNode = tempNode->next;
        }
        while(1)
        {
            if(tempNode == tNode && tempNode!=NULL)
            {
                return tNode;
            }
            else
            {
                tempNode = tempNode->next;
                tNode = tNode->next;
                if(tempNode == NULL)
                {
                    return NULL;
                }
            }
        }
        
        
    }
};
文章目录