C++, simple, get the length of diff


  • 0
    M

    /**

    • 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 || !headB)
      return NULL;

       // length of two lists
       unsigned int nLength1 = GetListLength(headA);
       unsigned int nLength2 = GetListLength(headB);
       
       ListNode *pListHeadLong = headA;
       ListNode *pListHeadShort = headB;
       int nLengthDiff = nLength1 - nLength2;
       if (nLength2 > nLength1) {
           pListHeadLong = headB;
           pListHeadShort = headA;
           nLengthDiff = nLength2 - nLength1;
       }
       
       for (int i = 0; i < nLengthDiff; i++) {
           pListHeadLong = pListHeadLong->next;
       }
       
       while(pListHeadLong &&
             pListHeadShort &&
             (pListHeadLong != pListHeadShort)) {
           pListHeadShort = pListHeadShort->next;
           pListHeadLong = pListHeadLong->next;
       }
       
       if (!pListHeadLong || !pListHeadShort)
           return NULL;
       
       // First intersection node
       ListNode *pFirstCommonNode = pListHeadLong;
       
       return pListHeadLong;
      

      }

      unsigned int GetListLength(ListNode* head) {
      unsigned int nLength = 0;
      ListNode *pNode = head;
      while(pNode != NULL) {
      ++nLength;
      pNode = pNode->next;
      }

       return nLength;
      

      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.