160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

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

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.

Thoughts

找到两个链表开始相交的点。两个链表如果等长，那两个指针一起往前走当相遇时就是交点。为了让长链表指针抛去多余的，让两个指针分别从两个头一起走，当其中一个撞到null时另一个到null的距离就是长的比短的多出去的部分。再让一个指针cur从长的头开始和剩下那个没撞到null的指针一起遍历直到撞到null，此时cur所在位置就是长的抛去多余的后所在位置。

Code

/*
 * @lc app=leetcode id=160 lang=cpp
 *
 * [160] Intersection of Two Linked Lists
 */

// @lc code=start
/**
 * 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 *cur_a = headA, *cur_b = headB;  
        while (cur_a != nullptr && cur_b != nullptr) {
            cur_a = cur_a->next;
            cur_b = cur_b->next;
        }
        ListNode *cur, *cur2, *flag;
        if (cur_a == nullptr) {
            cur = headB; 
            cur2 = headA; 
            flag = cur_b;
        } else {
            cur = headA; 
            cur2 = headB; 
            flag = cur_a;
        }
        while (flag != nullptr) {
            flag = flag->next;
            cur = cur->next;
        }
        while (cur != cur2) {
            cur = cur->next;
            cur2 = cur2->next;
        }
        return cur;
    }
};
// @lc code=end

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto len_a = len(headA), len_b = len(headB);
        auto head_a = headA, head_b = headB;
        if (len_a < len_b) {
            head_a = headB;
            head_b = headA;
        }
        for (int i = 0; i < abs(len_a - len_b); ++i) {
            head_a = head_a->next;
        }
        while (head_a != head_b) {
            head_a = head_a->next;
            head_b = head_b->next;
        }
        return head_a;
    }

private:
    int len(ListNode *head) {
        int res = 0;
        while (head != NULL) {
            head = head->next;
            ++res;
        }
        return res;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lenA = 0, lenB = 0;
        ListNode node = headA;
        while (node.next != null) {
            lenA++;
            node = node.next;
        }
        node = headB;
        while (node.next != null) {
            lenB++;
            node = node.next;
        }
        if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; i++) {
                headB = headB.next;
            }
        } else {
            for (int i = 0; i < lenA - lenB; i++) {
                headA = headA.next;
            }
        }

        while (headA != null && headB != null) {
            if (headA == headB) {
                return headB;
            }
            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }
}

Analysis

时间复杂度O(m+n).

还想到了另一种解法，把B的尾和A连上，环开始的点就是交叉点。