【数据结构】LeetCode160.相交链表 138.随即链表复制 牛客——链表回文问题

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA,*curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }

    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }

   

    int gap=abs(lenA-lenB);

    //假设法 先假设A长
    struct ListNode* longList=headA;
    struct ListNode* shortList=headB;
    if(lenA<lenB)
    {
        longList=headB;
        shortList=headA;
    }

    while(gap--)
    {
        longList=longList->next;
    }

    while(longList)
    {
        if(longList==shortList)
        return longList;
        longList=longList->next;
        shortList=shortList->next;
    }
    return NULL;
}

class PalindromeList {
public:
    //寻找中间节点
struct ListNode* middleNode(struct ListNode* head) {
    // 初始化快慢指针
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    // 移动指针直到fast到达链表末尾
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;      // 慢指针每次移动一步
        fast = fast->next->next; // 快指针每次移动两步
    }

    return slow; // 慢指针指向中间节点
}
    //反转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    if (n2)
        n3 = n2->next;
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}

    bool chkPalindrome(ListNode* A) {
        // write code here
        
    struct ListNode*mid=middleNode(A);
    struct ListNode*rmid=reverseList(mid);

    while(rmid&&A)
    {
        if(rmid->val!=A->val)
        return false;
        rmid=rmid->next;
        A=A->next;
       
    }
     return true;
}

};

struct Node* copyRandomList(struct Node* head) {

//拷贝节点插到原节点后边
struct Node*cur=head;

while(cur)
{
    struct Node* copy=(struct Node*)malloc(sizeof(struct Node));//分配内存
    copy->next=cur->next;
    cur->next=copy;
    copy->val=cur->val;

    cur=copy->next;//cur走到原链表的下一个  
}
//控制random

cur=head;
while(cur)
{
    struct Node* copy = cur->next;
    if(cur->random==NULL)//不要写成random==NULL
    {
        copy->random=NULL;
    }
    else
    {
        copy->random=cur->random->next;//核心代码
    }
    cur=copy->next;
}

//把拷贝链表尾插起来
struct Node* copyhead=NULL,*copytail=NULL;
 cur=head;
while(cur)
{
    struct Node*copy=cur->next;

    if(copytail==NULL)
    {
      copyhead=copytail=copy;
    }
    else
    {
        copytail->next=copy;
        copytail=copytail->next;
    
    }
    cur=copy->next;
}
return copyhead;
}