2020 - ARTS 2020-6-22 ~ 2020-6-28 - 《🌈 高行行的博客、周刊》

1. Algorithm(算法)
- LeetCode 160、剑指 Offer 52 相交链表
  - 参考链接
2. Review(点评)
3. Tip(技巧)
4. Share(分享)

ARTS是由左耳朵耗子陈皓在极客时间专栏《左耳听风》中发起的一个每周学习打卡计划。

Algorithm：至少做一个 LeetCode 的算法题。主要为了编程训练和学习。
Review：阅读并点评至少一篇英文技术文章。主要为了学习英文，如果你英文不行，很难成为技术高手。
Tip：学习至少一个技术技巧。主要是为了总结和归纳你日常工作中所遇到的知识点。
Share：分享一篇有观点和思考的技术文章。主要为了输出你的影响力，能够输出你的价值观。

1. Algorithm(算法)

LeetCode 160、剑指 Offer 52 相交链表

题目地址：剑指 Offer 52. 两个链表的第一个公共节点 160. 相交链表

解法1

public class Solution {
    /**
     * For example, the following two linked lists:
     A:          a1 → a2
     ↘
     c1 → c2 → c3
     ↗
     B:     b1 → b2 → b3
     begin to intersect at node c1.
     time : O(n);
     space : O(1);
     * @param headA
     * @param headB
     * @return
     */
    public a160_相交链表.cspiration.ListNode getIntersectionNode(a160_相交链表.cspiration.ListNode headA, a160_相交链表.cspiration.ListNode headB) {
        if (headA == null || headB == null) return null;
        /* 获取链表长度 */
        int lenA = len(headA);
        int lenB = len(headB);
        /* 将较长链表的指针向前移动 */
        if (lenA > lenB) {
            while (lenA != lenB) {
                headA = headA.next;
                lenA--;
            }
        } else {
            while (lenA != lenB) {
                headB = headB.next;
                lenB--;
            }
        }
        /* 同时移动两个元素，直到遇到相同元素 */
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
    public int len(ListNode head) {
        int len = 1;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
}

解法2

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 边界检查
        if (headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        // 如果a＆b有不同的len，那么我们将在第二次迭代后停止循环
        while (a != b) {
            // 对于第一次迭代的结束，我们只是将指针重置为另一个链表的头部
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}