【c数据结构】OJ练习篇 帮你更深层次理解链表！（相交链表、相交链表、环形链表、环形链表之寻找环形入口点、判断链表是否是回文结构、 随机链表的复制）

/**
 * 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) {
    //1. 遍历两个链表，求他们的长度差

    //设置两个链表头结点，方便遍历
    ListNode* l1 = headA;
    ListNode* l2 = headB;
    //设置变量存放链表长度，方便求差
    int sizeA=0,sizeB=0;

    //遍历计算两条链表长度ing
    while(l1){
        sizeA++;
        l1 = l1->next;
    }
    while(l2){
        sizeB++;
        l2 = l2->next;
    }
    //求长度差
    int gap = abs(sizeA-sizeB);//abs 绝对值函数


    //2.长链表先走长度差步
    //由于不知道哪个链表长，先随便定义再判断
    ListNode* longList = headB;
    ListNode* shortList = headA;
    if(sizeA > sizeB){
        longList = headA;
        shortList = headB;
    }
    //长链表先走
    while(gap--){
        longList = longList->next;
    }
    //此时的longList和shortList在同一起跑线
    

    //3. 遍历两个链表，要么相交，要么不相交
    while(longList && shortList)//条件是两个链表都不得是空
    {
        if(longList == shortList)//找到相同结点，相交
        {
            return longList;//反正相同结点，返回long 和short 都一样
        }
        //不相同，换下一结点继续比较
        longList = longList->next;
        shortList = shortList->next;
    }
    return NULL;//循环结束，可见不相交，返回空


}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    //创建快慢指针
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next){
        //慢指针走一步，快指针走两步，相当于快在一步一步追慢
        slow = slow ->next;
        fast = fast ->next->next;
        //相遇，说明带环
        if(fast == slow){
            return true;
        }
    }
    return false;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    //1. 找快慢指针相遇点->说明是环形结点
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast ->next){
        slow = slow ->next;
        fast = fast ->next->next;
        if(fast == slow)//找到相遇点！是环形
        {
            //2. 遍历头结点和快慢指针相遇点，每次一步，其相遇点就是环形入环第一个结点
            ListNode* pcur = head; //定义头结点
            while(pcur != fast){//但凡是环形，肯定会相遇
                pcur = pcur ->next;
                fast = fast ->next;
            }
            return pcur;
        }
    }
    return NULL;
}

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        //1. 找中间结点

        ListNode* slow = A;
        ListNode* fast = A;
        while(fast &&fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow;


        //2. 根据中间结点反转后面的链表

        ListNode* n1 = NULL;//指向空
        ListNode* n2 = mid;//指向中间结点
        ListNode* n3 = n2->next;//指向n2的下一个结点
        while(n2){
            n2->next = n1;//n2指向其前一个结点（初始是空）
            n1 = n2;//n1往后走
            n2 = n3;//n2往后走
            if(n3)//前提：n3不得为空，n3才能继续往后走
            n3 = n3->next;//n3往后走
        }
        ListNode* right =n1;//n1为我反转链表的头结点


        //3. 比较原链表和反转链表的结点

        ListNode* left = A;//原链表头结点
        while(right)//反转链表的尾结点是指向空的，当其走到空，说明遍历完了
        {
            if(left->val != right->val){//有不相等的值，说明不回文
                return false;
            }
            left = left->next;
            right = right->next;
        }
        return true;
    }
};

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
//复制链表结点
Node* buynode(int x){
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
//将复制的新链表插入原链表
void AddNode(Node* head){
    Node* pcur = head;//头结点
    while(pcur){
    Node* Next = pcur->next;//原链表的下一结点
    Node* newnode = buynode(pcur->val);//要复制的新结点
    
    newnode->next = Next;
    pcur->next = newnode;
    pcur = Next;//pcur走到下一结点
    }

}

struct Node* copyRandomList(struct Node* head) {
    if(head == NULL){
        return NULL;
    }
	//1. 原链表上复制结点
    //此时链表是 node1 -> newcopy1 -> node2 -> newcopy2-> node3..
    AddNode(head);
    //2. 赋值random
    Node* pcur = head;
    while(pcur){//循环修改random指针
        Node* copy = pcur->next;//此时pcur的下一结点即上一步插入的复制结点
        if(pcur->random != NULL){//因为创建新的节点时，直接让random指向空，现在只需将原链表中random不指向空的进行处理
            copy->random = pcur->random->next;
        }
        pcur = copy->next;//copy下一结点为原链表的下一结点
    }
    //3. 断开链表
    pcur = head;//让pcur回到头结点
    Node* newhead,*newtail;//为新链表创建头结点和要遍历连接的结点
    newhead = newtail = pcur->next;//pcur下一结点就是复制的新链表的头结点

    while(pcur->next->next)//因为有多插入复制的，所以pcur->next->next才是原链表下一结点
    {
        pcur = pcur->next->next;//pcur走到原链表下一结点
        newtail->next = pcur->next;//新链表连接新链表（被复制的）下一结点
        newtail = newtail->next;//新链表往后走
    }
    return newhead;//返回新链表头结点
}