算法闯关日记 Episode ：解锁链表新副本——破解「相交」迷局与「回文」谜题

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
   //求出两个链表的长度
   //创建临时变量，不改变链表结构
   ListNode* pa = headA;
   ListNode* pb = headB;
   int sizeA = 0, sizeB = 0;

   //循环求长度
   while(pa)
   {
        sizeA++;
        pa = pa->next;
   }

   while(pb)
   {
        sizeB++;
        pb = pb->next;
   }

   //长度差值，使用绝对值函数
   int gap = abs(sizeA - sizeB);
   
   //判断链表的长短
   ListNode* longlist = headA;
   ListNode* shortlist = headB;

   if(sizeA < sizeB)
   {
        longlist = headB;
        shortlist = headA;
   }

   //长链表先走gap步
   while(gap--)
   {
        longlist = longlist->next;
   }

   //同时遍历
   while(longlist)
   {
        //节点相同
        if(longlist == shortlist)
        {
            return longlist;
        }

        //节点不同
        longlist = longlist->next;
        shortlist = shortlist->next;
   }

   //没有相同的节点
   return NULL;
}

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList 
{
public:
    bool chkPalindrome(ListNode* A) 
    {
        // write code here
        //创建数组
        int arr[900] = {0};

        //遍历链表，将数值存放在数组中
        ListNode* pcur = A;
        int index = 0;
        while(pcur)
        {
            arr[index++] = pcur->val;
            pcur = pcur->next;
        }

        //创建左右指针，双方向遍历数组比较
        int left = 0;
        int right = index - 1;

        while(left < right)
        {
            if(arr[left] != arr[right])
            {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
};

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
  public:
    //找到中间节点
    ListNode* middleNode(struct ListNode* head) 
    {
        //创建快慢指针
        ListNode* fast, *slow;
 
        //首先都指向头节点
        fast = head;
        slow = head;
 
        //循环条件将两种情况都包含
        while(fast != NULL && fast->next != NULL)//条件换顺序？
        {
            //慢指针移动一节点
            slow = slow->next;
            //快指针移动两个节点
            fast = fast->next->next;
        }
 
        //返回slow
        return slow;
    }

    //从中间节点开始反转链表
    ListNode* reverseList(struct ListNode* head)
    {
        //创建三个指针
        ListNode* n1, * n2, * n3;
 
        //链表为空
        if (head == NULL)
        {
            return head;
        }
 
        //链表不为空
        //首先n1指向空
        n1 = NULL;
        n2 = head;
        n3 = n2->next;
        while (n2)//循环条件n2不为空（不超出链表）
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            //当n2到达尾节点时，n3为空，不能对空指针解引用
            if (n3)
            {
                n3 = n3->next;
            }
        }
        return n1;
    }

    bool chkPalindrome(ListNode* A) 
    {
        //找到中间节点
        ListNode* mid = middleNode(A);
        //从中间节点开始反转
        ListNode* right = reverseList(mid);
        //遍历原链表和反转之后的链表比较值是否相等
        ListNode* left = A;
        while (right) {
            if (right->val != left->val) 
            {
                return false;
            }
            right = right->next;
            left = left->next;
        }
        return true;
    }
};

🍓 我是晨非辰Tong！若这篇技术干货帮你打通了学习中的卡点：
👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长
❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量
⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用
💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑
🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解
技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！