interviewalgo
, ,
Source
Edit
History

160. 相交链表

Introduction

Question：160. 相交链表

解法一

Analysis

可以把问题转化成链表环起点的问题。

将 A 链表的末尾连接到 B 上，如果 A B 相交，那么此时 A 链表必有环，且环入口即为交点。

实现一个 next 函数，返回链表的下一个节点：

  • p->next != nullptr => p->next;
  • p->next == nullpter && p 在 A 上 => headB
  • others => nullpter;

Implement

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
ListNode *getIntersectionNode1(ListNode *headA, ListNode *headB) {
    if (headA == nullptr || headB == nullptr)
        return nullptr;
    ListNode *headAtail = nullptr;
    auto next = [headB, &headAtail](ListNode *p) -> ListNode* {
        if (p->next) return p->next;
        if (headAtail && p != headAtail)  return nullptr;
        headAtail = p;
        return headB;
    };

    ListNode *slow = next(headA);
    ListNode *fast = next(slow);
    while (fast && next(fast) && slow != fast)
    {
        fast = next(next(fast));
        slow = next(slow);
    }
    if (slow != fast) return nullptr;
    while (headA != slow)
    {
        headA = next(headA);
        slow = next(slow);
    }
    return headA;
}

解法二

Analysis

还是想复杂了

将 A B 首尾相连，这里首尾相连的设定是，A 末尾空节点的next是 headB，B 末尾空节点的next是 headA。然后从 A 和 B 同时遍历链表，当 A == B 时，就是交点。如果没有交点的话，交点就是 nullptr。

Implement

1
2
3
4
5
6
7
8
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *cur1 = headA, *cur2 = headB;
    while(cur1 != cur2){
        cur1 = cur1?cur1->next:headB;
        cur2 = cur2?cur2->next:headA;
    }
    return cur1;
}

One More Thing