Algorithm

本周做的算法题是 160. Intersection of Two Linked Lists。

问题描述

给定两个单链表，写一个函数找出其第一个相交的点。

例子：

        A:  a1 → a2 

                        ↘
                            c1 → c2 → c3 

                        ↗            
        B:  b1 → b2 → b3 

        begin to intersect at node c1.

思路

  1. 使用哈希表法，将遍历单链表A将其每个节点的地址存入哈希表中，再遍历单链表B，检测其节点是否在哈希表中，若存在则返回第一个相交的点。空间复杂度O(n),时间复杂度：O(n+m),其中n是链表A的长度，m是链表B的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Map<ListNode, ListNode> mapListNode = new HashMap<ListNode, ListNode>();
    if (null == headA || null == headB) {
        return null;
    }
    ListNode currHeadA = headA;
    ListNode currHeadB = headB;
    while (currHeadA != null) {
        mapListNode.put(currHeadA, currHeadA);
        currHeadA = currHeadA.next;
    }
    while (currHeadB != null) {
        if (mapListNode.get(currHeadB) != null) {
            return currHeadB;
        }
        currHeadB = currHeadB.next;
    }
    return null;
}
  1. 若能知道两个链表的长度差为diffLen，然后让长度长的链表先走diffLen部，接着遍历两个链表。若找到
    第一个相等的节点，即为相交的点。否则没有相交。时间复杂度O(n+m)，空间复杂度为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
 private int getLinkedLen(ListNode head) {
    int len = 0;
    while (head != null) {
        ++len;
        head = head.next;
    }
    return len;
}
    
public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
    if (null == headA || null == headB) {
        return null;
    }
    int headALen = getLinkedLen(headA);
    int headBLen = getLinkedLen(headB);
    int diffLen = headALen - headBLen;
    ListNode currA = headA;
    ListNode currB = headB;
    
    if (diffLen > 0) {
        while (diffLen != 0) {
            currA = currA.next;
            --diffLen;
        }
    } else {
        while (diffLen != 0) {
            currB = currB.next;
            ++diffLen;
        }
    }
    // process two list has no intersection node 
    while (currA != null && currA != currB) {
        currA = currA.next;
        currB = currB.next;
    }
    return currA == null ? null : currA;
}