首页 > 代码库 > [LeetCode] Intersection of Two Linked Lists

[LeetCode] Intersection of Two Linked Lists

2024-10-30 11:36:02   214人阅读

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:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

 

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

 

老题目了，复习一下。

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {12         ListNode *pA, *pB;13         int lenA, lenB;14         pA = headA; 15         lenA = 0;16         while (pA != NULL) {17             ++lenA;18             pA = pA->next;19         }20         pB = headB; 21         lenB = 0;22         while (pB != NULL) {23             ++lenB;24             pB = pB->next;25         }26         int idx = lenA > lenB ? (lenA - lenB) : (lenB - lenA);27         pA = headA; pB = headB;28         if (lenA > lenB) {29             while (idx--) {30                 pA = pA->next;31             }32         } else {33              while (idx--) {34                 pB = pB->next;35             }36         }37         while (pA != pB) {38             pA = pA->next;39             pB = pB->next;40         }41         return pA;42     }43 };

 

[LeetCode] Intersection of Two Linked Lists


联系
我们