Leetcode 160. 相交链表

题目

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解答

解法一：暴力解法

对 headA 链表的每一个结点，都判断在 headB 链表中是否存在。

纯暴力的解法，效率不太行。

复杂度：O(mn) 的时间，O(1) 的空间

代码

/**
 * 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) {
        for(ListNode p = headA; p != null; p = p.next) {
            for(ListNode q = headB; q != null; q = q.next) {
                if(q == p) return p;
            }
        }
        
        return null;
    }
}

结果

解法二：哈希法

比纯暴力好一点的解法，利用了哈希的特点来判断结点的存在性，降低了查找时的复杂度。

具体如下：

1. 遍历 headA 链表，在遍历过程中将结点放入 set 中。
2. 遍历 headB 链表，在遍历时判断当前结点是否存在于 set 中。
3. 若在 set 存在此结点，说明当前结点就是交点。
4. 否则继续遍历，直到为 q == null。
5. headB遍历完了都没找到交点，说明没有交点，返回 null 。

虽然不是纯暴力，但效率也不太行。

复杂度：O(m + n) 的时间，O(m) 的空间

代码

/**
 * 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) {
        Set<ListNode> set = new HashSet<>();
        
        ListNode p = headA;
        while(p != null) {
            set.add(p);
            p = p.next;
        }
        
        ListNode q = headB;
        while(q != null) {
            if(set.contains(q)) break;
            q = q.next;
        }
        
        return q;
    }
}

结果

解法三：两个栈倒序弹出

具体如下：

1. 使用两个栈保存两个链表的遍历结果。
2. 然后同时弹栈，如果两个栈弹出的结点不同，那么前一个结点就是最近的共同结点。

复杂度：O(m + n) 的时间，O(m + n) 的空间

代码

/**
 * 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) {
        LinkedList<ListNode> stackA = new LinkedList<>();
        LinkedList<ListNode> stackB = new LinkedList<>();
        
        while(headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        
        while(headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }
        
        ListNode res = null;
        while(!stackA.isEmpty() && !stackB.isEmpty()) {
            ListNode curA = stackA.pop();
            ListNode curB = stackB.pop();
            if(curA != curB) break;
            res = curA;
        }
        
        return res;
    }
}

结果

解法四：长链表先走 diff 步

解释一下 diff ：两个链表的长度差。

让长的链表先走 diff 步，然后两个链表一起走。

思想是：让长链表“变短”，从而达到消除长度差的目的。

复杂度：O(m + n) 的时间， O(1) 的空间。

代码

/**
 * 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) {
        int aLen = 0;
        int bLen = 0;
        ListNode p = headA;
        ListNode q = headB;
        while(p != null) {
            aLen ++;
            p = p.next;
        }
        
        while(q != null) {
            bLen ++;
            q = q.next;
        }
        
        p = headA;
        q = headB;
        int diff = Math.abs(aLen - bLen);
        for(int i = 0; i < diff; i ++) {
            if(aLen > bLen) {
                p = p.next;
            } else {
                q = q.next;
            }
        }
        
        while(p != q) {
            p = p.next;
            q = q.next;
        }
        
        return p;
    }
}

结果

解法五：短链表长度补齐

思想是：让短链表“变长”，从而消除长度差。

声明变量：p = headA，q = headB 。（注意：headA 是短链还是长链并不会影响结果，理解了下图就会明白。 ）

用一张图可以解决：

复杂度：O(m + n) 的时间， O(1) 的空间。

代码

/**
 * 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) {
        ListNode p = headA;
        ListNode q = headB;
        while(p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        
        return p;
    }
}

结果