4. 链表的回文结构

链接：OR36 链表的回文结构

描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

示例：

   测试样例：1->2->2->1

   返回：true

思路：

如果不加空间复杂度为O(1)的限制的话，那么我们可以创建一个数组，然后遍历链表，将链表中元素放到数组中，从数组前后开始遍历，判断是否是回文结构。

但是这里已经给定了要求，那我们便最好不要使用这种写法，所以我们要重新设计一个方法。

我们仔细想想，链表的回文结构，不就是从头开始向后遍历的元素和从后向前遍历的元素遍历到中间位置相等吗？

那么我们找到中间节点 mid，然后将 mid 开始的链表反转，将这个链表的起始节点给定为 reHead。然后奇偶情况遍历链表不就可以了吗？接下来我们展开讨论：

我们假定 reHead 已经反转，给定 curR来遍历 reHead，给定 curA 遍历 原链表 。

原链表为奇数个节点：curA、curR 同时开始走， reHead 先走完，当 curA 走到 reHead 的 前一个节点 时，并不会走到 rehead 。因为原链表的结构并没有改变，所以会走到原链表的下一个位置。所以不用担心 reHead 反转后链表表面上改变，而导致回文结构辨识不出的情况。(这样说可能有些模糊，但是没关系，马上有图解)

原链表为偶数个节点：curA、curR同时开始走，reHead先走完。这里由于 reHead 前和从 reHead 开始的节点个数相等，所以也就不需要想那么多。

结论：无论奇数偶数，只要 curA 和 curR 中有一个走到空就停止。

所以我们可以归纳一下这里的步骤：找中心节点 -> 反转中心节点开始的链表 -> 迭代判断。

而这里非常巧的是，我们上篇博客中已经写过了前两步——链表的中心节点、反转链表，所以到时候直接搬运即可~

注：C++兼容C的语法，所以用C的语法写完全可以。而且这道题目在力扣上没有限制空间复杂度，所以采用牛客网的~

代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast, *slow;
    fast = slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newNode = NULL;
    while (cur)
    {
        struct ListNode* next = cur->next;
        // 头插
        cur->next = newNode;
        newNode = cur;
        // cur迭代
        cur = next;
    }
    return newNode;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);
        struct ListNode* rHead = reverseList(mid);
        // A和rHead一般不会直接使用，拷贝一份
        struct ListNode* curA = A;
        struct ListNode* curR = rHead;
        while (curA && curR)
        {
            if (curA->val != curR->val)
            {
                return false;
            }
            curA = curA->next;
            curR = curR->next;
        }
        return true;
    }
};

5. 相交链表

链接：160. 相交链表

描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

   intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0

   listA - 第一个链表

   listB - 第二个链表

   skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数

   skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

   评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例1：

   输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

   输出：Intersected at ‘8’

   解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。

   从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。

   在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

   — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例2：

   输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

   输出：Intersected at ‘2’

   解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。

   从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。

   在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例3：

   输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

   输出：null

   解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。

   由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

   这两个链表不相交，因此返回 null 。

提示：

   listA 中节点数目为 m

   listB 中节点数目为 n

   1 <= m, n <= 3 * 10^4

   1 <= Node.val <= 10^5

   0 <= skipA <= m

   0 <= skipB <= n

   如果 listA 和 listB 没有交点，intersectVal 为 0

   如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

思路1：

如果要说这道题目，如果不考虑任何方法，那么就直接 暴力求解 。

取其中一条链表，让它的所有节点和另一条链表的所有元素比较。判断是否有交点，有则返回该节点；链表遍历完没有交点的话，返回空指针。

而且这次也出奇的巧，暴力求解在力扣上也能跑过~

但是在速度方面就很难看了，那我们能不能做出一些优化？看思路2↓

思路2(精讲)：

首先，我们要明确的一点是，只要两条链表 有交点 ，那么这两条链表的 尾结点 就是相等的。

因为单链表中存储的一部分是数据，一部分是下一个节点的地址，一个节点中只有一个 next ，所以以后链表走的都是一条路。

就像这样：

所以如果两个链表相交，就说明它们的 尾结点 肯定相同，那么遍历两条链表，比较它们的尾。

然后算出两条链表的长度，让长的链表走差值步。

那么让我长链表先走差值步，走到和短链表一样长，然后一起走，肯定就能找到交点了呀！找到交点后返回长链表、短链表节点中的任意一个。

注意点(已踩坑)：

当我们求长链表和短链表时，如果使用了三目操作符，比如：

 struct ListNode* longList = lenA > lenB ? headA : headB;
 struct ListNode* shortList = lenA < lenB ? headA : headB;

如果这样写，大多测试用例都能跑过，但是如果碰上一组两条链表的值相等的情况：

相交点 intersectVal：4

headA：②→③→④→⑤

headB：②→③→④→⑤

这样那么 longList 和 shortList 都是 headB，那么求相交点时，就直接返回第一个节点②了。

所以要控制 条件相同 ，让 longList 和 shortList 为不同的链表。

比如这样：

 struct ListNode* longList = lenA > lenB ? headA : headB;
 struct ListNode* shortList = lenA > lenB ? headB : headA;

注：可能是因为博主太菜，在这道题目 n 刷时，突然这么写了，找了半天没发现错误…希望大家不要踩坑…

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1, lenB = 1;
    // 这里 lenA 和 lenB 初始值其实关系不大
    // 主要是算它们的差值，所以即使 lenA 和 lenB初始化为 0 也能跑过
    // 但是由于是遍历到尾，所以 lenA 和 B 初始化为1是真正算出链表长度的
    while (tailA->next)
    {
        ++lenA;
        tailA = tailA->next;
    }
    while (tailB->next)
    {
        tailB = tailB->next;
        ++lenB;
    }
    if (tailA != tailB)
    {
        return NULL;
    }  
    struct ListNode* longList = lenA > lenB ? headA : headB;
    // 这里需要注意一下，两次三目表达式的条件最好一样
    // 否则链表的值相同时，可能会选取同一个链表
    // 导致结果错误，已踩坑
    struct ListNode* shortList = lenA > lenB ? headB : headA;
    int gap = abs(lenA - lenB);// 求差值
    while (gap--)
    {
        longList = longList->next;    
    }
    while (longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}

到这里本篇博客就到此结束了，这次的题目还是比较麻烦的，如果没完全理解可以画画图，多看看，多写写。

在下期，我依旧会为大家来带链表的OJ题，但是形式会和前两篇不太一样，我会用小剧场的形式，帮助大家在互动中带大家吃透链表中经典的问题！剧透一下，下一期内容会很精彩！我们敬请期待~

如果觉得anduin写的还不错的话，还请一键三连！如有错误，还请指正！

我是anduin，一名C语言初学者，我们下期见！