Leetcode/java/160.intersection-of-two-linked-lists.java at master · widmonstertony/Leetcode · GitHub

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
 * @lc app=leetcode id=160 lang=java
 *
 * [160] Intersection of Two Linked Lists
 */

// @lc code=start
/**
 * 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) {
    //     if (headA == null || headB == null) return null;
    //     ListNode a = headA, b = headB;
    //     while (a != b) {
    //         a = (a != null) ? a.next : headB;
    //         b = (b != null) ? b.next : headA;
    //     }
    //     return a;
    // }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode ptrA = headA, ptrB = headB;
        while (true) {
            // 如果两个node相等，则尝试能否一直走到底，不能的话就不是答案
            if (ptrA == ptrB) {
                ListNode ansNode = ptrA;
                while (ptrA.next != null && ptrB.next != null) {
                    ptrA = ptrA.next;
                    ptrB = ptrB.next;
                    if (ptrA != ptrB) {
                        break;
                    }
                }
                if (ptrA != ptrB) {
                    ansNode = null;
                }
                return ansNode;
            }
            // 如果不是的话，就往后移一位
            else {
                if (ptrA.next != null && ptrB.next != null) {
                    ptrA = ptrA.next;
                    ptrB = ptrB.next;
                }
                // 如果两个中有一个已经到末尾了，则移去另一个列表的开头
                else if (ptrA.next == null && ptrB.next != null) {
                    ptrA = headB;
                    ptrB = ptrB.next;
                }
                else if (ptrB.next == null && ptrA.next != null){
                    ptrB = headA;
                    ptrA = ptrA.next;
                }
                // 如果两个都到末尾了，说明没有答案
                else {
                    break;
                }
            }
        }
        return null;
    }
}
// @lc code=end