DAY6 - 链表(二)

今天继续写链表，整理几题比较需要思考的题目，直接进例题
链表的题目没什麽模板或是固定思路..所以就放几题经典的

例题实战

138. 复制带随机指针的链表
往前复制一份再断开~~不算很直观

/*
// 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 nullptr;
        }
        //每个Node复制一份
        Node* curr = head;
        while(curr){
            Node* copy = new Node(curr->val);
            Node* nnext = curr->next;
            curr->next = copy;
            copy->next = nnext;
            curr = curr->next->next;
        }
        curr = head;
        //链random指针
        while(curr){
            Node* copy = curr->next;
            if(copy&&curr->random)
                copy->random = curr->random->next;
            curr = curr->next->next;
        }
        //分离
        curr = head;
        Node* new_head = head->next;
        while(curr->next->next){
            Node* old = curr;
            Node* nnew = curr->next;
            old->next = old->next->next;
            nnew->next = nnew->next->next;
            curr = old->next;
        }
        curr->next->next = nullptr;
        curr->next = nullptr;
        return new_head;
    }
};

142. 环形链表 II
判断有环无环也算很经典的问题吧(?
但解决方法很简单，这类问题就用一个快指针(一次移动两步)，一个慢指针(一次移动一步)，看最後快指针能不能倒追到慢指针(就有环)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    // ListNode* res;
    // unordered_map<ListNode*, bool> hash;
public:
    ListNode *detectCycle(ListNode *head) {
        // if(dfs(head)==false){
        //     return NULL;
        // }
        // return res;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!=NULL && fast->next!=NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow==fast){
                ListNode* p = head;
                while(p!=slow){
                    p = p->next;
                    slow = slow->next;
                }
                return p;
            }
        }
        return NULL;
    }
    // bool dfs(ListNode* head){
    //     if(head==NULL || head->next ==  NULL){
    //         return NULL;
    //     }
    //     if(hash[head]!=NULL){
    //         res = head;
    //         return true;
    //     }
    //     else{
    //         cout<< hash[head];
    //         hash[head] = true;
    //         return dfs(head->next);
    //     }
    //     return false;
    // }
};

19. 删除链表的倒数第 N 个结点
倒数N就先让一个指针先跑N步另一个从起点出发，等前面的指针走到终点，就是倒数N了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //双指针
        ListNode* temp = head;
        ListNode* f = head;
        ListNode* s = head;
        while(n--){
            f = f->next;
        }
        if(f==NULL){
            return head->next;
        }
        while(f->next!=NULL){
            f = f->next;
            s = s->next;
        }
        s->next = s->next->next;
        return temp;
    }
};