第三期：那些年，我们一起经历过的链表中的浪漫

PS：每道题解题方法不唯一，欢迎讨论！每道题后都有解析帮助你分析做题，答案在最下面，关注博主每天持续更新。

1. 两个链表的第一个公共节点

“我走过我的世界，再从你的世界走一遍”
“你走过你的世界，再从我的世界走一遍”
“最终我们将相遇，可能在途中，可能在结尾。”
题目描述
输入两个链表，返回它们的公共节点。如没有公共节点返回null。
示例1
输入：listA = [1,2,3,4,5], listB = [6,7,2,3,4,5]
输出：value为8的节点
示例2
输入：listA = [1,2,3,4,5,6,7], listB = [8,9,6,7]
输出：value为6的节点
解析
这道题可以运用哈希集合，直接把一个链表的所以节点放入，然后在遍历另一条链表节点，遍历到第一个集合包含的节点，便是公共节点，返回此节点。如没有，返回null。
但这样空间复杂空为O(M + N);那有没有空间复杂度为O(1)的方法呢？答案是有的，这就要请出我们浪漫的双指针了。
我们构建两个节点指针p1， p2，p1 = headA，p2 = headB，让它们分别遍历自己的链表，在途中如果 p1 == p2，则返回p1 ，或则当p1 == null时，让p1 = headB，p2 == null时，p2 = headA，继续遍历，这次一定会经历p1 == p2，返回p1即可。
一句话：
你变成我，走过我走过的路。
我变成你，走过你走过的路。
然后我们便相遇了。
两个节点不断的寻找对方的身影，双向奔赴的爱情，岂不浪漫。

2.链表中间节点

题目描述
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例1
输入：[1,2,3,4,5]
输出:value值为3的节点
示例2
输入：[1,2,3,4]
输出:value值为3的节点
解析
为了找到你想要的，我可以忍受孤独，我可以付出一切，我愿意先行。
这道题也可以运用双指针，定义两个指针，一个是慢指针slow，另一个是快指针fast。初始，慢指针slow和快指针fast都指向链表的头节点。然后，快指针fast每次向前移动两步，慢指针slow每次向前移动一步，当快指针fast不能继续向前移动时，慢指针slow所指的节点就是中间节点。

答案

1.两个链表中第一公共节点

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //如果这个世界没有你
        if (headA == null || headB == null) {
            //我活着又有什么意义
            return null;
        }
        //为了寻找你
        ListNode pA = headA, pB = headB;
        //我们彼此开始努力
        while (pA != pB) {
            //在这平行世界中携手共进
            //寻找彼此的踪迹
            //没人把这当作游戏
            //互相探寻对方世界的奥秘
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        //是的，爱情能够创造奇迹
        //我们永远不分离
        return pA;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.链表中间节点

    public ListNode middleNode(ListNode head) {
        //你说你喜欢那个东西
        ListNode slow = head;
        ListNode fast = head;
        //我愿意忍受孤独，先行
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //祝你安好
        return slow;
    }
1
2
3
4
5
6
7
8
9
10
11
12