Leetcode Intersection of Two Linked Lists

10350 ワード

/**

 * 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) {

        int lena = count(headA);

        int lenb = count(headB);

        int diff = 0;

        ListNode* longer = NULL;

        ListNode* shorter= NULL;

        if (lena > lenb) {

            diff = lena - lenb;

            longer = headA;

            shorter= headB;

        } else {

            diff = lenb - lena;

            longer = headB;

            shorter= headA;

        }

        longer = forward(longer, diff);

        

        while (longer != shorter) {

            longer = forward(longer, 1);

            shorter= forward(shorter, 1);

        }

        return longer;

    }

    ListNode* forward(ListNode* head, int step) {

        while(head != NULL) {

            if (step-- <= 0) {

                break;

            }

            head = head->next;

        }

        return head;

    }

    int count(ListNode* head) {

        int res = 0;

        while (head != NULL) {

            head = head->next;

            res++;

        }

        return res;

    }

};

Leetcodeも可視化され、ますますハイエンドになりました
第2ラウンド:
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.
  •  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  // 20:08
    
    10 class Solution {
    
    11 public:
    
    12     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
    13         ListNode* cura = headA;
    
    14         ListNode* curb = headB;
    
    15         
    
    16         int na = 0, nb = 0;
    
    17         
    
    18         while (cura != NULL) {
    
    19             na++;
    
    20             cura = cura->next;
    
    21         }
    
    22         
    
    23         while (curb != NULL) {
    
    24             nb++;
    
    25             curb = curb->next;
    
    26         }
    
    27         ListNode* prewalk = NULL;
    
    28         
    
    29         int diff = 0;
    
    30         if (na > nb) {
    
    31             prewalk = headA;
    
    32             diff = na - nb;    
    
    33         } else if (na < nb) {
    
    34             prewalk = headB;
    
    35             diff = nb - na;
    
    36         }
    
    37         while (diff--) {
    
    38             prewalk = prewalk->next;
    
    39         }
    
    40         
    
    41         cura = headA;
    
    42         curb = headB;
    
    43         
    
    44         if (na > nb) {
    
    45             cura = prewalk;
    
    46         } else if (na < nb){
    
    47             curb = prewalk;
    
    48         }
    
    49         
    
    50         while (cura != curb) {
    
    51             cura = cura->next;
    
    52             curb = curb->next;
    
    53         }
    
    54         return cura;
    
    55     }
    
    56 };