[数据结构与算法]链表一些题（II）

1.链表回文结构

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        if(A==nullptr&&A->next==nullptr)
            return true;
        //栈：先进后出
        //队列：先进先出
        //正好遍历时，遍历数据的顺序是相反的
        ListNode* cur=A;
        while(cur)
        {
            ListNode* next=cur->next;
            s.push(cur->val);
            q.push(cur->val);
            cur=next;
        }
        while(!s.empty()&&!q.empty())
        {
            if(s.top()!=q.front())
            {
                return false;
            }
            else
            {
                return true;
            }
            s.pop();
            q.pop();
        }
        return true;
    }
    stack<int> s;
    queue<int> q;
};

2.求两个链表第一个公共节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA,*curB;
        curA=headA;
        curB=headB;
        int lenA=0;
        int lenB=0;
        //先求两个支路的长度
        while(curA)
        {
            ++lenA;
            curA=curA->next;
        }
        while(curB)
        {
            ++lenB;
            curB=curB->next;
        }
        curA=headA;
        curB=headB;
        //谁长谁先走
        if(lenA>lenB)
        {
           int gapA=lenA-lenB;
            while(gapA--)
            {
                curA=curA->next;
            }
        }
        if(lenA<lenB)
        {
            int gapB=lenB-lenA;
            while(gapB--)
            {
                curB=curB->next;
            }
        }
        //这时候curA和curB在同一起跑线上
        while(curA&&curB)
        {
            if(curA==curB)
            {
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        return nullptr;
    }
};

3.判断链表是否有环

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast,*slow;
        fast=slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
            //如果快慢指针相遇则有换
            if(fast==slow)
            {
                return true;
            }
        }
        return false;

        
    }
};

4.环的入口位置

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* hascyle(ListNode* head)
    {
        ListNode* fast,*slow;
        fast=slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow)
            {
                return fast;
            }
        }
        return nullptr;
    }
    ListNode *detectCycle(ListNode *head) {
        //第一个位置：相遇节点的位置
        //第二个位置：头结点位置
        //这两个位置相遇的位置为入环的位置
        ListNode* cur=hascyle(head);
        if(cur)
        {
            while(cur)
            {
                if(cur==head)
                {
                    return cur;
                }
                cur=cur->next;
                head=head->next;
            }
        }
        return nullptr;
        
    }
    
};

5.拷贝一个链表

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr)
        {
            return head;
        }
        Node* cur=head;
       
        //拷贝数据
        while(cur)
        {
            //开辟一个新的节点
            Node* newnode=new Node(cur->val);
            //拷贝新的数据
            Node* next=cur->next;
            newnode->next=next;
            cur->next=newnode;
            cur=newnode->next;

        }
        //拷贝指针
        cur=head;
        while(cur)
        {
            Node* copy=cur->next;
            if(cur->random)
            {
                copy->random=cur->random->next;
            }
            else
            {
                copy->random=nullptr;
            }
            cur=copy->next;

        }
        //拆链
        Node* newhead=nullptr;
        cur=head;
        while(cur)
        {
            Node* copy=cur->next;
            Node* next=copy->next;
            cur->next=next;
            if(newhead==nullptr)
            {
                newhead=copy;
            }
            if(next)
            {
                copy->next=next->next;
            }
            cur=next;
        }
        return newhead;
        
    }
};