http://www.geeksforgeeks.org/write-a-function-to-get-the-intersection-point-of-two-linked-lists/
第一第二个方法比较简单，下面这段代码是第三个方法
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <string> 7 #include <fstream> 8 #include <map> 9 #include <set> 10 using namespace std; 11 12 struct node { 13 int data; 14 node *next; 15 node() : data(0), next(NULL) { } 16 node(int d) : data(d), next(NULL) { } 17 }; 18 19 void push(node* &head, int k) { 20 node *new_node = new node(k); 21 new_node->next = head; 22 head = new_node; 23 } 24 25 void print(node* head) { 26 while (head) { 27 cout << head->data << " "; 28 head = head->next; 29 } 30 cout << endl; 31 } 32 33 int getintersect(node *first, node *second) { 34 int c1 = 0; 35 int c2 = 0; 36 node *p = first; 37 while (p) { 38 c1++; 39 p = p->next; 40 } 41 p = second; 42 while (p) { 43 c2++; 44 p = p->next; 45 } 46 if (c1 < c2) { 47 swap(c1, c2); 48 swap(first, second); 49 } 50 while (c1 != c2) { 51 c1--; 52 first = first->next; 53 } 54 while (first != second) { 55 first = first->next; 56 second = second->next; 57 } 58 return second->data; 59 } 60 61 int main() { 62 node *head = new node(3); 63 head->next = new node(6); 64 head->next->next = new node(9); 65 head->next->next->next = new node(15); 66 head->next->next->next->next = new node(30); 67 node *second = new node(10); 68 second->next = head->next->next->next; 69 cout << getintersect(head, second); 70 return 0; 71 }
第四第五个方法不太容易想到