ARTS 2020-6-22 ~ 2020-6-28

2020-06-27

字数统计: 841 | 阅读时长≈ 3 分钟

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;
    }
}