編寫一個程式,找到兩個單鏈表相交的起始節點。 例如,下麵的兩個鏈表: 在節點 c1 開始相交。 註意: 如果兩個鏈表沒有交點,返回 null. 在返回結果後,兩個鏈表仍須保持原有的結構。 可假定整個鏈表結構中沒有迴圈。 程式儘量滿足 O(n) 時間複雜度,且僅用 O(1) 記憶體。 ...
編寫一個程式,找到兩個單鏈表相交的起始節點。
例如,下麵的兩個鏈表:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
在節點 c1 開始相交。
註意:
- 如果兩個鏈表沒有交點,返回
null
. - 在返回結果後,兩個鏈表仍須保持原有的結構。
- 可假定整個鏈表結構中沒有迴圈。
- 程式儘量滿足 O(n) 時間複雜度,且僅用 O(1) 記憶體。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *A=headA; struct ListNode *B=headB; while(A!=B) { if (NULL == A) { A=headB; } else { A=A->next; } if (NULL == B) { B=headA; } else { B=B->next; } } return B; }