(Leetcode) Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

Your code should preferably run in O(n) time and use only O(1) memory.

More efficient solution:
Maintain two pointer na and nb, initially pointing to the head of the two lists. Traverse the two lists at the same pace. When nA reaches the end of the list, then redirect it to the head of B; when nB reaches the end of the list, redirect it the head of A!

This solution is more elegant as it takes care of both the cases either list a is longer or list b is longer.

/**
 * 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;

        ListNode *na = headA, *nb = headB;
        traverseAndRedirect(na,nb,headA,headB);
        traverseAndRedirect(na,nb,headA,headB);

        while (na && nb && na != nb) {
            na = na->next;
            nb = nb->next;
        }

        return na;
    }

    void traverseAndRedirect(ListNode* &na, ListNode* &nb, ListNode* &headA, ListNode* &headB) {
        while (na && nb) {
            na = na->next;
            nb = nb->next;
        }

        if (!na) {
            na = headB;
        } else if (!nb) {
            nb = headA;
        }
    }
};

Solution that passed all tests:

/**
 * 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) {
        ListNode *pa = headA, *pb = headB;
        while (pa && pb) {
            pa = pa->next;
            pb = pb->next;
        }

        if (pa && !pb)
            return getIntersectionNode(headB,headA);

        ListNode* pb2 = headB;
        while (pb) {
            pb = pb->next;
            pb2 = pb2->next;
        }

        pa = headA, pb = pb2;
        while (pa && pb && pa != pb) {
            pa = pa->next;
            pb = pb->next;
        }

        return pa;

    }
};