IntersectionOfTwoLinkedLists [source code]

public class IntersectionOfTwoLinkedLists {
static
/******************************************************************************/
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode tailA = reverse(headA);
        ListNode tailB = reverse(headB);
        ListNode curA = tailA, curB = tailB;
        ListNode prev = curA;
        while (curA != null && curB != null && curA == curB) { 
            prev = curA;
            curA = curA.next;
            curB = curB.next;
        }
        reverse(tailA);
        reverse(tailB);
        return prev == curA ? null : prev;
    }

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        IntersectionOfTwoLinkedLists2.Solution tester = new IntersectionOfTwoLinkedLists2.Solution();
        int[][] inputs = {
            {1,2,3,4}, {9,8}, {5, 6, 7},
            {1}, {}, {},
            {1,3,5,7,9,11,13,15,17,19,21}, {2}, {},
            {}, {}, {1,2,3,4,5,6,7,8,9,10,11,12,13},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            System.out.println(Printer.seperator());
            ListNode h1 = ListNode.buildListNode(inputs[3 * i]);
            ListNode h2 = ListNode.buildListNode(inputs[1 + 3 * i]);
            ListNode h3 = ListNode.buildListNode(inputs[2 + 3 * i]);
            if (h1 == null) h1 = h3;
            else ListNode.attach(h1, h3);
            if (h2 == null) h2 = h3;
            else ListNode.attach(h2, h3);
            Printer.openColor("red");
            System.out.print(ListNode.serialize (h1) + " AND " + ListNode.serialize (h2));
            Printer.closeColor();
            System.out.println(" -> " + ListNode.serialize (tester.getIntersectionNode(h1, h2)));
            Printer.openColor("green");
            System.out.println(ListNode.serialize (h1) + " AND " + ListNode.serialize (h2));
            Printer.closeColor();
        }
    }
}

刚开始想写一个 reverse 居然也磕磕巴巴写不出来; 后来总结了一下, 其实我对于 reverse 的思路还是没有完全理解; 就算是这个一个循环跑完的 reverse, 最后实际上过程中, 也是有两个 list 同时存在的: 分别是 head 领头的old list, 和由 prev 领头的new list;
代码本身的顺序上面, 这个是一个head&prev的标准的伸脚算法, 更新的顺序应该是: 在更新 head 之前, 先更新 prev, 来存住 head 当前的值, 这样以后再改变 head 的值, 才不会担心丢失;

while 的 header 里面是什么? yes-condition: on what condition do you want the loop to run? what does it mean for the loop to run? that is to go further. Then, what is the condition that you want the two pointers to go further? 这样分析, 就不会搞乱了;

注意这里的&& in header的使用: 其实还是相当于一个合法性检查的顺序: to make sure subsequent dot access is lega;

所以LinkedList 的很多问题确实是可以用各种 routine 来解决, 比如这个题目我感觉 reverse 就很好用;

reverse这样的 routine 不允许复制粘贴, 就是要自己一个字一个字的敲出来.

另外虽然这个题目给的图什么的也是两个 list intersection 的画法, 你实际思考的时候, 还是最好分开成两个 list 来思考: 电脑是不知道什么 intersection 不 intersection 的, 如果你用一个指针 iterate listA, 那么这个时候这个指针知道的就是这个 list, 至于有没有其他的 list 切入进来, 这个iterating 的指针是不知道的;

不过这个代码最后过不了 OJ? 不知道哪里出问题了, 就是这里的 case4死活过不了; ver2里面有一个明确修改了 input 的 val 的, 试了一下也过了; 不过他那个没有修改 structure, 可能是这个原因;

看了一下 discussion 里面的讨论, 好像很多人认为这一题就算最后还原了, 也算是改变了 input; 我感觉题目好像没有要求始终保持不变? 只要求retain original AFTER return;

正确的答案和 opt 全都放在 ver2里面了;
这个问题不知道为什么我没有想到那个补偿长度的算法, 按理来说那个算法其实是很简单的; 也许 intersection 问题可以适当总结一下? 尤其是尝试用2pointers 来做的 intersection?

另外这一题也出现了一个新的需求: no modification?
这个也许也可以总结出一些类似的切入点?

感觉我还是没有掌握简单升级的思路: 首先你应该想, 如果给你的是两个等长度的 list, 你会不会做? 当然会做, 这个很简单(刚开始不要立刻就从最 general, 也就是长度不相等的情况开始思考). 但是我们现在长度不相等, 那么为什么之前的做法就不行了呢? 局限性在哪里? 你能不能修改一下来弥补这个局限性;

Problem Description

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.
  Credits:
  Special thanks to @stellari for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:134.4K
Total Submissions:440.5K
Contributor: LeetCode
Companies
amazon microsoft bloomberg airbnb
Related Topics
linked list
Similar Questions
Minimum Index Sum of Two Lists