160.相交链表

发表于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。

【题目】

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

分析：对我而言，这道问题的关键在于相交的定义。相交之后的全部节点都是相同的。因此如果存在相交，两个链表的末端应该是相等的。那么最长的情况就是，长的链表完全包含短的链表。所以我们需要对两个链表进行尾端对齐。

【解答】

1、 尾端对齐

时间复杂度O（m+n）,空间复杂度O（1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 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 = 0;
        int lenB = 0;
        ListNode* curA = headA;
        ListNode* curB = headB;
        //获得链表A长度
        while (curA -> next != NULL) {
            lenA++;
            curA = curA -> next;
        }
        //获得链表B长度
        while (curB -> next != NULL) {
            lenB++;
            curB = curB -> next;
        }
        //将curA curB置位
        curB = headB;
        curA = headA;
        //将长度更长的置为 A
        while (lenA < lenB) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        int n = lenA - lenB;
        while (n--) {
            curA = curA -> next;
        }
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA -> next;
            curB = curB -> next;
        }
        return NULL;
    }
};