LeetCode hot100@链表 – 瓜皮coding

单链表定义方式：

 struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

STL链表：
list<int> mylist; 是一个双向循环链表，不需要关心节点管理和内存管理(详细语法见c++提高编程)

160. 相交链表

gap

 /**
 * 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 =  headA;
        ListNode *curB =  headB;
        int lenA = 1;
        int lenB = 1;
        while(curA->next != NULL) {
            curA = curA->next;
            lenA++;
        }
        while(curB->next != NULL) {
            curB = curB->next;
            lenB++;
        }
        // cout << "lenA = " << lenA << endl;
        // cout << "lenB = " << lenB << endl;
        
        curA = headA;
        curB = headB;
        if(lenA > lenB) {
            swap(curA, curB);
            swap(lenA, lenB);
        }
 
        int gap = lenB - lenA;
        for(int i = 0; i < gap; i++) curB = curB->next;
        // cout << "val = " << (*curB).val << endl;
        while(curB != NULL) {
            if(curB == curA) return curA;
            curA = curA->next;
            curB = curB->next;
        }
 
        return NULL;
    }
};

206. 反转链表

双指针法

 /**
 * 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* reverseList(ListNode* head) {
        ListNode *cur = head;
        ListNode *pre = nullptr;
        ListNode *tmp = nullptr;
 
        while(cur) {
            //先用tmp保存一下后一个节点，因为一会方向改变了，就找不到它了
            tmp = cur->next; 
 
            cur->next = pre; //改变方向
            pre = cur; //pre往后移一步
            cur = tmp; //把之前保存的后一个节点还给cur
        }
 
        return pre; //此时cur已经出界了
    }
};

234. 回文链表

把val用数组存起来再判断就简单了，因为可以双向遍历

 /**
 * 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:
    bool isPalindrome(ListNode* head) {
        ListNode *cur = head;
        vector<int> v;
        while(cur) {
            v.push_back(cur->val);
            cur = cur->next;
        }
 
        int left = 0, right = v.size() - 1;
        while(left < right) {
            if(v[left++] != v[right--]) return false;
        }
 
        return true;
    }
};

141. 环形链表

Solution1：用哈希存节点地址是否被访问过

Solution2：如果一个链表存在环，那么快慢指针必然会相遇(第二次相遇时快慢指针移动次数差值即为环的长度)

 class Solution1 {
public:
    bool hasCycle(ListNode *head) {
        unordered_map<ListNode*, int> mp;
        ListNode *cur = head;
        while(cur) {
            if(mp[cur]) {
                return true;
            }
            mp[cur]++;
            cur = cur->next;
        }
 
        return false;
    }
};

 class Solution2 {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast) {
            fast = fast->next;
            if(fast) {
                fast = fast->next;
            }
            //先判断再移动慢指针，否则会漏掉只有一个节点的情况
            if(fast == slow) return true; 
            slow = slow->next;  
        }
 
        return false;
    }
};

142. 环形链表 II

用哈希存节点地址是否被访问过

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map<ListNode*, int> mp;
        ListNode *cur = head;
        while(cur) {
            if(mp[cur]) {
                return cur;
            }
            mp[cur]++;
            cur = cur->next;
        }
 
        return NULL;
    }
};

21. 合并两个有序链表

优秀的链表语法练习题

 /**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *merge = new ListNode(); //先创建一个虚拟结点作为新链表头节点的前一个节点
        ListNode *cur = merge; //跟踪新链表尾部
        ListNode *cur1 = list1;
        ListNode *cur2 = list2;
  
        while(cur1 != nullptr && cur2 != nullptr) {
            if(cur1->val < cur2->val) {
                cur->next = cur1;
                cur = cur->next;
                cur1 = cur1->next;
            } else {
                cur->next = cur2;
                cur = cur->next;
                cur2 = cur2->next;
            }
        }
 
        if(cur1 == nullptr) cur->next = cur2;    
        else if(cur2 == nullptr) cur->next = cur1;    
 
        return merge->next;
    }
};

2. 两数相加

模拟相加，无需转换，最后统一处理进位更简单

 class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *res = new ListNode();
        ListNode *cur = res;
        ListNode *cur1 = l1;
        ListNode *cur2 = l2;
        bool carry_bit = false; 
 
        while(cur1 && cur2) {
            cur->next = new ListNode(cur1->val + cur2->val);
            cur = cur->next;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
 
        while(cur1) {
            cur->next = new ListNode(cur1->val);
            cur = cur->next;
            cur1 = cur1->next;
        }
        while(cur2) {
            cur->next = new ListNode(cur2->val);
            cur = cur->next;
            cur2 = cur2->next;
        }
 
        cur = res->next;
        while(cur) {
            if(cur->val >= 10) {
                cur->val -= 10;
                if(cur->next) cur->next->val += 1;
                else cur->next = new ListNode(1);
            }
            cur = cur->next;
        }
 
        return res->next; 
    }
};

19. 删除链表的倒数第 N 个结点

双指针 + 虚拟头节点

ps：一般需要处理头节点的时候就可以加一个虚拟头节点，比如头节点可能为空的情况

 class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode();
        dummy->next = head;
        ListNode *cur = dummy;
        ListNode *pre = dummy;
 
        while(n--) {
            pre = pre->next;
        } 
        while(pre->next) {
            pre = pre->next;
            cur = cur->next;
        }
 
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete(tmp);
 
        return dummy->next;
    }
};

24. 两两交换链表中的节点

三个节点

 class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy = new ListNode();
        dummy->next = head;
        ListNode *cur = dummy;
 
        while(cur->next && cur->next->next) {
            ListNode *tmp1 = cur->next; //存下第一个节点
            ListNode *tmp2 = cur->next->next->next; //存下第三个节点
 
            cur->next = tmp1->next;
            cur->next->next = tmp1;
            tmp1->next = tmp2;
 
            cur = cur->next->next;
        }
 
        return dummy->next;
    }
};

25. K 个一组翻转链表

不能用哈希存一下节点地址，然后两两交换，那样只是节点的位置变了，但是next指针没变化，也就是说连线没有变化，把线扯成直线后，还是1→2→3

其实就是206.反转链表复杂版，k个一组进行反转

 /**
 * 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 {
private:
    ListNode* myReverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* tmp = nullptr;
        while(cur) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
public:
    //反转链表复杂版
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy = new ListNode();
        dummy->next = head;
        ListNode *cur = dummy;
        int n = k;
 
        while(cur) {
            ListNode *first = cur; //first指向0
            //如果遍历后链表长度不足k 则退出
            while(cur && cur->next && n) {
                cur = cur->next;
                n--;
            }
            if(n) break;
            //cur指向3（以样例2举例）
            ListNode *next_node = cur->next; //next_node指向4
            cur->next = nullptr; //断开连接 防止调用反转函数时超过k还一直运行下去
            ListNode *tail = first->next; //tail指向1
            first->next = myReverse(tail); 
            tail->next = next_node; //反转后的尾部1指向next_node4
            cur = tail; //新一轮的起始点 即4的前一个节点
            n = k;
        }
         
        return dummy->next; 
    }
};

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) {
        Node *cur = head;
        unordered_map<Node*, Node*> mp;
 
        while(cur) {
            mp[cur] = new Node(cur->val);   
            cur = cur->next;
        }
 
        cur = head;
        while(cur) {
            //新节点的next指向旧节点的下一个节点的新节点
            mp[cur]->next = mp[cur->next]; 
            mp[cur]->random = mp[cur->random];
            cur = cur->next;
        }
 
        return mp[head];  
    }
};

148. 排序链表

不需要用到原节点的地址，只需新节点的val值不变就行，想复杂了

 /**
 * 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* sortList(ListNode* head) {
        ListNode *res = new ListNode();
        ListNode *cur = head;
 
        vector<int> v;
        while(cur) {
            v.push_back(cur->val);
            cur = cur->next;
        }
        ranges::sort(v);
      
        cur = res;
        for(const auto &i : v) {
            cur->next = new ListNode(i);
            cur = cur->next;
        }
 
        return res->next;
    }
};

23. 合并 K 个升序链表

优先队列（底层逻辑是堆排序）

 class Solution {
public:
    struct Comparator { //自定义比较器
        bool operator()(ListNode *a, ListNode *b) {
            return a->val > b->val; //升序 即小根堆
        }
    };
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Comparator> pq;
        //遍历每一条链表的每一个节点
        for(auto &list_cur : lists) { //注意不能加const 因为list_cur一直在改变
            while(list_cur) {
                pq.push(list_cur);
                list_cur = list_cur->next;
            }
        }
        
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        //从队列中不断取出节点并连接
        while(!pq.empty()) {
            cur->next = pq.top();
            cur = cur->next;
            pq.pop();
        }
        cur->next = nullptr; //标志链表结束
 
        return dummy->next;
    }
};

146. LRU 缓存

很多的语法练习题 细节不少但可惜用单链表写了半天 debug变天最后几个样例超时

最后用STL中的 list(双向循环链表) + 复杂map

很好的STL练习题

 class LRUCache {
private:
    int cpy = 0;
    list<pair<int, int>> m_list; //双向链表存k、v
    unordered_map<int, list<pair<int, int>>::iterator> mp; //map存k到list迭代器的映射
public:
    LRUCache(int capacity) {
        cpy = capacity;
    }
    
    int get(int key) {
        //如果不存在
        if(mp.find(key) == mp.end()) return -1;
        else {
            //key存在 需要用splice函数更新key对应节点在链表中的位置 
            //更新到链表头部 代表最近使用
            m_list.splice(m_list.begin(), m_list, mp[key]);
            return mp[key]->second;
        }
    }
 
    void put(int key, int value) {
        //如果key存在 调用get已经更新到头部 再更新value
        if(get(key) != -1) mp[key]->second = value;
        else { //key不存在
            if(m_list.size() >= cpy) { //如果满了 先从尾部删一个 map也要删
                mp.erase(m_list.back().first);
                m_list.pop_back();
            } 
            m_list.push_front(pair(key, value)); //在头部插入新元素
            mp[key] = m_list.begin(); //把新元素存到map中
        }
    }
};
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */