链表相交

题目

给定两个单链表的头节点headA和headB，找出并返回两个单链表相交的起始节点，若两个链表没有交点，返回null。

思路

• 链表如果相交，最后的节点一定是相同的；
• 从后往前看，某个链表长度比较多时，一定是没有用的，那么就需要先计算链表长度，统一从链表节点相同的部分开始比较；
• 有相同节点值的节点不一定就是相交开始的地方，要比较指针相同；

具体代码

Cpp

include <iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/**
 * 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 nullptr;
        }
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        ListNode *curA = headA;
        ListNode *curB = headB;
        int test = abs(lenA - lenB);
        if (lenA > lenB)
        {
            while (test--)
                curA = curA->next;
        }
        else
        {
            while (test--)
                curB = curB->next;
        }
        while (curA)
        {
            if (&curA == &curB)
                return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
    int getLength(ListNode *headA)
    {
        int res = 0;
        ListNode *cur = headA;
        while (cur)
        {
            cur = cur->next;
            res++;
        }
        return res;
    }
};

int main()
{
    Solution s;
    ListNode *headA = new ListNode(1);
    ListNode *curA = headA;
    for (int i = 2; i <= 5; i++)
    {
        curA->next = new ListNode(i);
        curA = curA->next;
    }
    ListNode *headB = new ListNode(1);
    ListNode *curB = headB;
    for (int i = 2; i <= 5; i++)
    {
        curB->next = new ListNode(i);
        curB = curB->next;
    }
    curB->next = curA;
    curA = headA;
    while (curA != nullptr)
    {
        cout << curA->val << " ";
        curA = curA->next;
    }
}

Java

/**
 * 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 = getLength(headA);
        int lenB = getLength(headB);
        ListNode curA = headA;
        ListNode curB = headB;

        if (lenA > lenB) {
            while (lenA > lenB) {
                curA = curA.next;
                lenA--;
            }
        } else {
            while (lenB > lenA) {
                curB = curB.next;
                lenB--;
            }
        }

        while (curA != null) {
            if (curA != curB) {
                curA = curA.next;
                curB = curB.next;
            } else {
                return curB;
            }
        }
        return null;
    }

    public int getLength(ListNode head) {
        int res = 0;
        while (head != null) {
            res++;
            head = head.next;
        }
        return res;
    }
}