本题为简单难度的链表题，解决方法有很多，思维有一定难度。

注意，每个链表都具有头结点，设其中str1和str2的长度分别为 n1 和 n2。

方法一：哈希表

判断两个链表是否相交，可以使用哈希集合存储链表结点。

首先遍历链表str1，并将链表str1中的每个包含关键字的结点加入哈希集合中。然后遍历链表 str2，对于遍历到的每个结点，判断该结点是否在哈希集合中：

如果当前结点不在哈希集合中，则继续遍历下一个结点；

如果当前结点在哈希集合中，则后面的结点都在哈希集合中，即从当前结点开始的所有结点都在两个链表的相交部分，因此在链表str2中遍历到的第一个在哈希集合中的结点就是两个链表相交的结点，返回该结点。

如果链表str2中的所有结点都不在哈希集合中，则两个链表不相交，返回NULL。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "uthash.h"

struct ListNode {
    int data;
    struct ListNode *next;
};

struct HashTable {
    struct ListNode *key;
    UT_hash_handle hh;
};

struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
    struct HashTable *hashTable = NULL;
    struct ListNode *temp = str1->next;
    while (temp != NULL) {
        struct HashTable *tmp;
        HASH_FIND(hh, hashTable, &temp, sizeof(struct HashTable *), tmp);
        if (tmp == NULL) {
            tmp = malloc(sizeof(struct HashTable));
            tmp->key = temp;
            HASH_ADD(hh, hashTable, key, sizeof(struct HashTable *), tmp);
        }
        temp = temp->next;
    }
    temp = str2->next;
    while (temp != NULL) {
        struct HashTable *tmp;
        HASH_FIND(hh, hashTable, &temp, sizeof(struct HashTable *), tmp);
        if (tmp != NULL) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

struct ListNode** createTwoLinkedList(char *s1, char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail1 = head1;
    struct ListNode* intersection_node = NULL;
    int p1 = 0;
    while (p1 < len1) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s1[p1];
        node->next = NULL;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s2[p2];
        node->next = NULL;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    struct ListNode* hs[] = {head1, head2};
    return hs;
}

int main() {
    char *s1 = "loading";
    char *s2 = "being";
    struct ListNode** strs = createTwoLinkedList(s1, s2);
    struct ListNode* str1 = strs[0];
    struct ListNode* str2 = strs[1];
    struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != NULL) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

注：C语言没有提过哈希表，可以采用三方开源uthash。

C++代码如下（含测试用例）：

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;

struct ListNode {
    int data;
    ListNode *next;
};

ListNode *getIntersectionNode(ListNode *str1, ListNode *str2) {
    unordered_set<ListNode *> visited;
    ListNode *temp = str1->next;
    while (temp != nullptr) {
        visited.insert(temp);
        temp = temp->next;
    }
    temp = str2->next;
    while (temp != nullptr) {
        if (visited.count(temp)) {
            return temp;
        }
        temp = temp->next;
    }
    return nullptr;
}

vector<ListNode *> createTwoLinkedList(string s1, string s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    ListNode* head1 = new ListNode();
    ListNode* tail1 = head1;
    ListNode* intersection_node = nullptr;
    int p1 = 0;
    while (p1 < len1) {
        ListNode* node = new ListNode();
        node->data = s1[p1];
        node->next = nullptr;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    ListNode* head2 = new ListNode();
    ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        ListNode* node = new ListNode();
        node->data = s2[p2];
        node->next = nullptr;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    return vector<ListNode *>{head1, head2};
}

int main() {
    string s1 = "loading";
    string s2 = "being";
    vector<ListNode *> strs = createTwoLinkedList(s1, s2);
    ListNode* str1 = strs[0];
    ListNode* str2 = strs[1];
    ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != nullptr) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n1+n2) 。需要遍历两个链表各一次。
• 空间复杂度： O(n1) 。需要使用哈希集合存储链表str1中的全部包含关键字的结点。

方法二：辅助栈

从后往前遍历两个链表，找到最后一个相同的结点。利用栈先进后出的性质，将两条链表分别压入两个栈中，然后循环比较两个栈的栈顶元素，同时记录上一位栈顶元素。当遇到第一个不同的结点时，结束循环，上一位栈顶元素即是答案。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 101

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
    struct ListNode *stk1[MAXSIZE], *stk2[MAXSIZE];
    int stk1_top = 0, stk2_top = 0;
    struct ListNode *p1 = str1->next, *p2 = str2->next;
    while (p1 != NULL) {
        stk1[stk1_top++] = p1;
        p1 = p1->next;
    }
    while (p2 != NULL) {
        stk2[stk2_top++] = p2;
        p2 = p2->next;
    }
    struct ListNode *ans = NULL;
    while (stk1_top && stk2_top) {
        if (stk1[--stk1_top] == stk2[--stk2_top]) {
            ans = stk1[stk1_top];
        } else {
            break;
        }
    }
    return ans;
}

struct ListNode** createTwoLinkedList(char *s1, char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail1 = head1;
    struct ListNode* intersection_node = NULL;
    int p1 = 0;
    while (p1 < len1) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s1[p1];
        node->next = NULL;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s2[p2];
        node->next = NULL;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    struct ListNode* hs[] = {head1, head2};
    return hs;
}

int main() {
    char *s1 = "loading";
    char *s2 = "being";
    struct ListNode** strs = createTwoLinkedList(s1, s2);
    struct ListNode* str1 = strs[0];
    struct ListNode* str2 = strs[1];
    struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != NULL) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

struct ListNode {
    int data;
    ListNode *next;
};

ListNode *getIntersectionNode(ListNode *str1, ListNode *str2) {
    stack<ListNode *> s1, s2;
    for (ListNode *p = str1->next; p != nullptr; p = p->next) {
        s1.push(p);
    }
    for (ListNode *p = str2->next; p != nullptr; p = p->next) {
        s2.push(p);
    }
    ListNode *ans = nullptr;
    while (!s1.empty() && !s2.empty()) {
        if (s1.top() == s2.top()) {
            ans = s1.top();
        } else {
            break;
        }
        s1.pop();
        s2.pop();
    }
    return ans;
}

vector<ListNode *> createTwoLinkedList(string s1, string s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    ListNode* head1 = new ListNode();
    ListNode* tail1 = head1;
    ListNode* intersection_node = nullptr;
    int p1 = 0;
    while (p1 < len1) {
        ListNode* node = new ListNode();
        node->data = s1[p1];
        node->next = nullptr;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    ListNode* head2 = new ListNode();
    ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        ListNode* node = new ListNode();
        node->data = s2[p2];
        node->next = nullptr;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    return vector<ListNode *>{head1, head2};
}

int main() {
    string s1 = "loading";
    string s2 = "being";
    vector<ListNode *> strs = createTwoLinkedList(s1, s2);
    ListNode* str1 = strs[0];
    ListNode* str2 = strs[1];
    ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != nullptr) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n1+n2) 。需要遍历两个链表各一次。
• 空间复杂度： O(n1+n2) 。需要使用辅助栈存储链表str1和str2中的全部包含关键字的结点。

方法三：双指针（差值法）

使用双指针的方法，可以将空间复杂度降至 O(1) 。

创建两个指针 p1和 p2 ，初始时分别指向str1和str2的头结点，分别遍历两条链表，得到链表长度分别为 l1 和 l2 （不考虑头结点），计算两条链表长度差值 |l1−l2| ，然后将指针 p1和 p2 重新分别指向str1和str2的头结点，长的链表的指针先的走过差值长度|l1−l2| ，然后两个指针 p1和 p2 同步遍历两条链表，当指针 p1 和 p2 指向同一个结点或者都为空时，返回它们指向的结点或者NULL。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
    int l1 = 0;
    int l2 = 0;
    struct ListNode *p1 = str1->next, *p2 = str2->next;
    while (p1 != NULL) {
        l1++;
        p1 = p1->next;
    }
    while (p2 != NULL) {
        l2++;
        p2 = p2->next;
    }
    p1 = str1->next;
    p2 = str2->next;
    if (l1 > l2) {
        int d = l1 - l2;
        while (d > 0) {
            p1 = p1->next;
            d--;
        }
    } else if (l1 < l2) {
        int d = l2 - l1;
        while (d > 0) {
            p2 = p2->next;
            d--;
        }
    }
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

struct ListNode** createTwoLinkedList(char *s1, char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail1 = head1;
    struct ListNode* intersection_node = NULL;
    int p1 = 0;
    while (p1 < len1) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s1[p1];
        node->next = NULL;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s2[p2];
        node->next = NULL;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    struct ListNode* hs[] = {head1, head2};
    return hs;
}

int main() {
    char *s1 = "loading";
    char *s2 = "being";
    struct ListNode** strs = createTwoLinkedList(s1, s2);
    struct ListNode* str1 = strs[0];
    struct ListNode* str2 = strs[1];
    struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != NULL) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ListNode {
    int data;
    ListNode *next;
};

ListNode* getIntersectionNode(ListNode* str1, ListNode* str2) {
    int l1 = 0;
    int l2 = 0;
    ListNode *p1 = str1->next, *p2 = str2->next;
    while (p1 != nullptr) {
        l1++;
        p1 = p1->next;
    }
    while (p2 != nullptr) {
        l2++;
        p2 = p2->next;
    }
    p1 = str1->next;
    p2 = str2->next;
    if (l1 > l2) {
        int d = l1 - l2;
        while (d > 0) {
            p1 = p1->next;
            d--;
        }
    } else if (l1 < l2) {
        int d = l2 - l1;
        while (d > 0) {
            p2 = p2->next;
            d--;
        }
    }
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

vector<ListNode *> createTwoLinkedList(string s1, string s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    ListNode* head1 = new ListNode();
    ListNode* tail1 = head1;
    ListNode* intersection_node = nullptr;
    int p1 = 0;
    while (p1 < len1) {
        ListNode* node = new ListNode();
        node->data = s1[p1];
        node->next = nullptr;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    ListNode* head2 = new ListNode();
    ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        ListNode* node = new ListNode();
        node->data = s2[p2];
        node->next = nullptr;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    return vector<ListNode *>{head1, head2};
}

int main() {
    string s1 = "loading";
    string s2 = "being";
    vector<ListNode *> strs = createTwoLinkedList(s1, s2);
    ListNode* str1 = strs[0];
    ListNode* str2 = strs[1];
    ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != nullptr) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n1+n2) 。需要遍历两个链表各一次。
• 空间复杂度： O(1) 。需要常数个辅助变量。

方法四：双指针（交替法）

方法二可以进一步改写，使得代码更加简洁，采用指针交替的方式省略差值的计算。

创建两个指针 p1和 p2 ，初始时分别指向str1和str2的第一个结点，然后将两个指针依次遍历两个链表的每个结点。具体做法如下：

每步操作需要同时更新指针 p1和 p2 。

• 如果指针 p1不为空，则将指针 p1 移到下一个结点；如果指针 p2 不为空，则将指针 p2 移到下一个结点。
• 如果指针 p1 为空，则将指针 p1 移到链表str2的头结点；如果指针 p2 为空，则将指针 p2 移到链表str1的头结点。

当指针 p1 和 p2 指向同一个结点或者都为空时，返回它们指向的结点或者NULL。

思路证明：

情况一：两个链表相交

假设链表str1的不相交部分有 a 个结点，链表str2的不相交部分有 b 个结点，两个链表相交的部分有 c 个结点，则有 a+c=n1∧b+c=n2 。

• 如果 a=b ，则两个指针会同时到达两个链表相交的结点，此时返回相交的结点；
• 如果 a≠b ，则指针 p1 会遍历完链表str1，指针 p2 会遍历完链表str2，两个指针不会同时到达链表的尾结点，然后指针 p1 移到链表str2的头结点，指针 p2 移到链表str1的头结点，然后两个指针继续移动，在指针 p1 移动了 a+c+b 次、指针 p2 移动了 b+c+a 次之后，两个指针会同时到达两个链表相交的结点，该结点也是两个指针第一次同时指向的结点，此时返回相交的结点。

情况二：两个链表不相交

• 如果 n1=n2 ，则两个指针会同时到达两个链表的尾结点，然后同时变成空值NULL，此时返回 NULL；
• 如果 n1≠n2 ，则由于两个链表没有公共结点，两个指针也不会同时到达两个链表的尾结点，因此两个指针都会遍历完两个链表，在指针 p1 移动了 n1+n2 次、指针 p2 移动了 n1+n2 次之后，两个指针会同时变成空值 NULL，此时返回NULL。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *str1, struct ListNode *str2) {
    if (str1->next == NULL || str2->next == NULL) {
        return NULL;
    }
    struct ListNode *p1 = str1->next, *p2 = str2->next;
    while (p1 != p2) {
        p1 = p1 == NULL ? str2->next : p1->next;
        p2 = p2 == NULL ? str1->next : p2->next;
    }
    return p1;
}

struct ListNode** createTwoLinkedList(char *s1, char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    struct ListNode* head1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail1 = head1;
    struct ListNode* intersection_node = NULL;
    int p1 = 0;
    while (p1 < len1) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s1[p1];
        node->next = NULL;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    struct ListNode* head2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = s2[p2];
        node->next = NULL;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    struct ListNode* hs[] = {head1, head2};
    return hs;
}

int main() {
    char *s1 = "loading";
    char *s2 = "being";
    struct ListNode** strs = createTwoLinkedList(s1, s2);
    struct ListNode* str1 = strs[0];
    struct ListNode* str2 = strs[1];
    struct ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != NULL) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ListNode {
    int data;
    ListNode *next;
};

ListNode *getIntersectionNode(ListNode *str1, ListNode *str2) {
    if (str1->next == nullptr || str2->next == nullptr) {
        return nullptr;
    }
    ListNode *p1 = str1->next, *p2 = str2->next;
    while (p1 != p2) {
        p1 = p1 == nullptr ? str2->next : p1->next;
        p2 = p2 == nullptr ? str1->next : p2->next;
    }
    return p1;
}

vector<ListNode *> createTwoLinkedList(string s1, string s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    int suffix_len = 0;
    for (int i = len1 - 1, j = len2 - 1; i >= 0, j >= 0; i--, j--) {
        if (s1[i] == s2[j]) {
            suffix_len++;
        } else {
            break;
        }
    }
    ListNode* head1 = new ListNode();
    ListNode* tail1 = head1;
    ListNode* intersection_node = nullptr;
    int p1 = 0;
    while (p1 < len1) {
        ListNode* node = new ListNode();
        node->data = s1[p1];
        node->next = nullptr;
        tail1->next = node;
        tail1 = tail1->next;
        if (p1 == len1 - suffix_len) {
            intersection_node = node;
        }
        p1++;

    }
    ListNode* head2 = new ListNode();
    ListNode* tail2 = head2;
    int p2 = 0;
    while (p2 < len2) {
        ListNode* node = new ListNode();
        node->data = s2[p2];
        node->next = nullptr;
        tail2->next = node;
        tail2 = tail2->next;
        p2++;
        if (p2 == len2 - suffix_len) {
            node->next = intersection_node;
            break;
        }
    }
    return vector<ListNode *>{head1, head2};
}

int main() {
    string s1 = "loading";
    string s2 = "being";
    vector<ListNode *> strs = createTwoLinkedList(s1, s2);
    ListNode* str1 = strs[0];
    ListNode* str2 = strs[1];
    ListNode* intersectionNode = getIntersectionNode(str1, str2);
    if (intersectionNode != nullptr) {
        printf("%c", intersectionNode->data);
    }
    return 0;
}

复杂度分析

• 时间复杂度： O(n1+n2) 。需要遍历两个链表各一次。
• 空间复杂度： O(1) 。需要常数个辅助变量。