/** * 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 nullptr || headB nullptr) { return nullptr; } ListNode* pA headA; // 遍历链表A的每个节点 while (pA ! nullptr) { ListNode* pB headB; // 遍历链表B的每个节点查找是否有相同地址的节点 while (pB ! nullptr) { if (pA pB) { // 比较节点地址而不是值 return pA; } pB pB-next; } pA pA-next; } return nullptr; } };class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode * visited; ListNode *temp headA; while (temp ! nullptr) { visited.insert(temp); temp temp-next; } temp headB; while (temp ! nullptr) { if (visited.count(temp)) { return temp; } temp temp-next; } return nullptr; } };class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return nullptr; // 计算链表长度 int lenA 0, lenB 0; ListNode *pA headA, *pB headB; while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } // 重新指向头节点 pA headA; pB headB; // 让长的先走差值步 int diff abs(lenA - lenB); if (lenA lenB) { while (diff--) pA pA-next; } else { while (diff--) pB pB-next; } // 同时移动找交点 while (pA pB) { if (pA pB) return pA; pA pA-next; pB pB-next; } return nullptr; } };class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA nullptr || headB nullptr) { return nullptr; } ListNode *pA headA, *pB headB; while (pA ! pB) { pA pA nullptr ? headB : pA-next; pB pB nullptr ? headA : pB-next; } return pA; } };
LeetCodehot100-160 相交链表
/** * 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 nullptr || headB nullptr) { return nullptr; } ListNode* pA headA; // 遍历链表A的每个节点 while (pA ! nullptr) { ListNode* pB headB; // 遍历链表B的每个节点查找是否有相同地址的节点 while (pB ! nullptr) { if (pA pB) { // 比较节点地址而不是值 return pA; } pB pB-next; } pA pA-next; } return nullptr; } };class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_setListNode * visited; ListNode *temp headA; while (temp ! nullptr) { visited.insert(temp); temp temp-next; } temp headB; while (temp ! nullptr) { if (visited.count(temp)) { return temp; } temp temp-next; } return nullptr; } };class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (!headA || !headB) return nullptr; // 计算链表长度 int lenA 0, lenB 0; ListNode *pA headA, *pB headB; while (pA) { lenA; pA pA-next; } while (pB) { lenB; pB pB-next; } // 重新指向头节点 pA headA; pB headB; // 让长的先走差值步 int diff abs(lenA - lenB); if (lenA lenB) { while (diff--) pA pA-next; } else { while (diff--) pB pB-next; } // 同时移动找交点 while (pA pB) { if (pA pB) return pA; pA pA-next; pB pB-next; } return nullptr; } };class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA nullptr || headB nullptr) { return nullptr; } ListNode *pA headA, *pB headB; while (pA ! pB) { pA pA nullptr ? headB : pA-next; pB pB nullptr ? headA : pB-next; } return pA; } };
