数据结构_回文，相交题-2.4

做题后觉得，这些算法都不算编程语言层面东西了，这和数学更为接近，我讨厌数学！虽然由思路转为代码是代码能力没错，但更关键的思路还是偏向数学层面的求解。

一. 判断是否为回文单链表

从首结点看和从末尾结点看整个链表是一样的就是回文。

a. 想到的思路：把值放数组里比呗

1）快慢指针定位中点；
2）从中点向后取值放入一个数组中；
3）反向比较数组与慢指针继续走的值；
4）一样就是回文链表，不一样就不是。

遇到的问题：要分奇偶，先判断奇偶

链表为偶数，思路没问题。为奇数，是必出错的。
解决方法：偶数正常比，奇数中间自己和自己比。

个人思路的缺陷

1）链表扯上数组就是愚笨的，即转为地址空间连续的数据处理。
2）那你数组开多大的呢？题目要是没说明呢？（这里是C语言本身的缺陷，C++就是不必固定数组空间大小，希望我没有说错）

代码

bool isPalindrome(struct ListNode* head) {
   
    int arr[100000] = {
    0 };
    Node* fast = head;
    Node* slow = head;
    int i = 1;
    int odd = 0;
    arr[0] = head->val;
    while (fast)
    {
   
        fast = fast->next;
        if (fast == NULL)奇数跳出现NULL说明为奇数
            odd = 1;

        if (fast)
            fast = fast->next;

        if (fast)
        {
   
            slow = slow->next;
            arr[i] = slow->val;
            i++;
        }


    }
    int num = 0;

    if (i > 1) 
        num = i;
    else
    {
   
        num = 1;
    }

    if (slow->next == NULL)只有一个元素的考虑
        return true;

    if (odd == 0)奇数不动，偶数进一位
    {
   
        slow = slow->next;
    }
    
    for (i = 0; i < num; i++)
    {
   
        if (arr[num - i - 1] != slow->val)
        {
   
            return false;
        }
        if (slow)
            slow = slow->next;

    }
    return true;

}

b. 参考思路

1）快慢指针定位一半；
2）翻转后面的链表；（不必考虑数组开辟多少空间）
3）比较两个链表是否一样。

增益点：链表问题尽量不涉及数组

上面也写到了。

代码

typedef struct ListNode Node;
bool isPalindrome(struct ListNode* head){
   
    
    Node* fast=head;
    Node* slow=head;
    Node* storeslow=NULL;

    while(fast)    中点
    {
   
        fast=fast->next;
        if(fast)
        fast=fast->next;
        storeslow=slow;
        slow=slow->next;
    }
    storeslow->next=NULL;

    Node* n1=NULL;
    Node* n2=slow;
    Node* n3=NULL;

    while(n2) 翻转链表
    {
   
        if(n2->next)
        n3=n2->next;

        n2->next=n1;

        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    while(n1&&head)比较两个链表
    {
   
        if(n1->val!=head->val)
        return false;

        n1=n1->next;
        head=head->next;
    }
    return true;
}

二. 判断两个链表是否相交

a. 想到的思路：*->next一样不就相交了吗？

1）headA遍历的同时，遍历headB；
2）出现相等的地址就相交了；
3）一方结束到NULL，就没相交。

缺陷：复杂度

1）O(N^2)

看参考思路的疑惑

双指针必须要互相有数量关系才能用，我都不知道A,B的长度，我怎么用双指针？

代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   
   if(headA==NULL||headB==NULL)
   return NULL;
    
   struct ListNode * storeB=headB;
    while(headA)
    {
   
        headB=storeB;
  		while(headB)
    	{
   
    
        	if(headA==headB)
        	{
   
            	return headA;
        	}
        	else
        	{
   
            	headB=headB->next;
        	}
       }
       headA=headA->next;
       }
    return NULL; 
}

b. 参考思路

1）求headA长度，求haedB长度；
2）长度相减；
3）让长的一方先走那么多步，双指针定位。

增益点一：没有数量关系，你不会自己创造出来吗？？？？

你都疑惑不等长怎么在遍历的同时，判断是否相交，你就自己创造让二者同步。
你的快慢指针的二倍速不也是自己创造出来的？怎么到这就忘了创造？

增益点二：链表长度真的像之前想的那样没意义吗？

别那么死板，要用长度，就求。

代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   
   if(headA==NULL||headB==NULL)
   return NULL;
    struct ListNode * storeA=headA;
   struct ListNode * storeB=headB;
   int lA=0;
   int lB=0;
   int L=0;
    while(storeA->next)
    {
   
        storeA=storeA->next;
        lA++;
    }
    while(storeB->next)
    {
   
        storeB=storeB->next;
        lB++;
    }
    
    if(lA>=lB)
    {
   
        L=lA-lB    /A先走
        while(L--)
        {
   
            if(headA)
            headA=headA->next;
        }
    }
    else
    {
   
        L=lB-lA;    /B先走
        while(L--)
        {
   
            if(headB)
            headB=headB->next;
        }
    }
        while(headA)        /等长
        {
   
            if(headA==headB)
            return headA;
            headA=headA->next;
            headB=headB->next;
        }
        return NULL;

}