160. 相交鏈表-有解無憂

撰寫一個程式，找到兩個單鏈表相交的起始節點，如下面的兩個鏈表：

在節點 c1 開始相交，示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3輸出：Reference of the node with value = https://www.cnblogs.com/i-8023-/p/8輸入解釋：相交節點的值為 8 （注意，如果兩個串列相交則不能為 0），從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]，在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點，示例 2：

輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1輸出：Reference of the node with value = https://www.cnblogs.com/i-8023-/p/2輸入解釋：相交節點的值為 2 （注意，如果兩個串列相交則不能為 0），從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]，在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點，示例 3：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2輸出：null輸入解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]，由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值，解釋：這兩個鏈表不相交，因此回傳 null，注意：如果兩個鏈表沒有交點，回傳 null.在回傳結果后，兩個鏈表仍須保持原有的結構，可假定整個鏈表結構中沒有回圈，程式盡量滿足 O(n) 時間復雜度，且僅用 O(1) 記憶體，來源：力扣（LeetCode）鏈接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，思路1遍歷鏈表 A，將 A中節點對應的指標（地址），插入 set遍歷鏈表 B，將 B中節點對應的指標（地址），在 set 中查找，不回傳 end()的第一個地址，即交點

 1 class Solution { 2 public: 3     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 4         set<ListNode*> node_set; 5         while (headA) { 6             node_set.insert(headA); 7             headA = headA->next; 8         } 9         while (headB) {10             if (node_set.find(headB) != node_set.end()) { //find()沒找到，回傳 end()11                 return headB;12             }13             headB = headB->next;14         }15         return NULL;16     }17 };

思路 2計算鏈表長度和長度之差

將長鏈表指標移動到和短鏈表對齊

headA 和 headB 同時移動，直到兩指標指向同一節點

 1 class Solution { 2 public: 3     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 4         int list_A_len = getListLength(headA); 5         int list_B_len = getListLength(headB); 6         if (list_A_len > list_B_len) { 7             headA = forwardLongList(headA, list_A_len, list_B_len); 8         } else { 9             headB = forwardLongList(headB, list_B_len, list_A_len);10         }11         while (headA && headB) {12             if (headA == headB) {13                 return headA;14             }15             headA = headA->next;16             headB = headB->next;17         }18         return NULL;19     }20 private:21     //計算鏈表長度22     int getListLength(ListNode* head) {23         int len = 0;24         while (head) {25             ++len;26             head =  head->next;27         }28         return len;29     }30    31     //將長鏈表指標向后移動，回傳對齊后的位置32     ListNode* forwardLongList(ListNode* long_head, int long_len, int short_len) {33         int delta = long_len - short_len;34         while (long_head && delta) {35             long_head = long_head->next;36             --delta;37         }38         return long_head;39     }40 };

測驗

 1 int main(int argc, const char * argv[]) { 2     ListNode a1(1); 3     ListNode a2(2); 4     ListNode b1(3); 5     ListNode b2(4); 6     ListNode b3(5); 7     ListNode c1(6); 8     ListNode c2(7); 9     ListNode c3(8);10     a1.next = &a2;11     a2.next = &c1;12     c1.next = &c2;13     c2.next = &c3;14     b1.next = &b2;15     b2.next = &b3;16     b3.next = &c1;17     18     Solution solve;19     ListNode *result = solve.getIntersectionNode(&a1, &b1);20     cout <<result->val;21 22     return 0;23 }

View Code

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/87994.html

標籤：C++

上一篇：C++工程師養成每日一題（vector使用）

下一篇：最小生成樹兩個經典演算法（Prime演算法、Kruskal演算法） - biaobiao88