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:
null.1、自己算法
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) return NULL; struct ListNode *tmp1 = head->next; //这里使用了head->next；所以head == NULL判断必须放上面 struct ListNode *tmp2 = head; if(head->next == NULL) return head; head = head->next; tmp2->next = NULL; while(head->next != NULL) { head = head->next; tmp1->next = tmp2; tmp2 = tmp1; tmp1 = head; } head->next = tmp2; return head; } struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *tailA = reverseList(headA); struct ListNode *tailB = reverseList(headB); struct ListNode *tmpA = NULL; struct ListNode *tmpB = NULL; struct ListNode *tmpA2 = tailA; struct ListNode *tmpB2 = tailB; while(tailA && tailB) { if(tailA == tailB) { tmpA = tailA; tmpB = tailB; tailA = tailA->next; tailB = tailB->next; } else { reverseList(tmpA2); reverseList(tmpB2); return tmpA; } } return NULL; }
2、使用网上的方法
？？？Intersection of Two Linked Lists
原文：http://www.cnblogs.com/dylqt/p/4839520.html