花生_TL007

这个屌丝很懒，什么也没留下！

热门标签

leetcode(2) | 单链表（c++）

作者：花生_TL007 | 2024-04-09 23:13:49

踩

链表题目经验总结

一、Easy

1.Reverse Linked List

2. Palindrome Linked List

3.Remove Duplicates from Sorted List

4.Remove Duplicates from Sorted List II

5.Add Two Numbers

二、mid

1.Reverse Linked List II

2.Reorder List

3.linked-list-cycle

4.Linked List Cycle II

5.Remove Nth Node From End of List

6.Rotate List

7.Copy List with Random Pointer

8.Partition List

9.Odd Even Linked List

三、hard

1.LRU Cache

2.Swap Nodes in Pairs

3.Reverse Nodes in k-Group

链表题目经验总结

1.头插法：https://blog.csdn.net/yyw_lucky3/article/details/64923059

2.链表的题目注意dummy head的使用，可以有助于解题

3.使用指针时，*h，此时使用h->next；使用非指针时，h，h.next，注意区别

一、Easy

1.Reverse Linked List

Reverse a singly linked list.

Example:


Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

思路：考虑为空的情况


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode* cur = head,* temp;
        // 注意这里的cur->next，cur保证[]情况不会出错
        while(cur && cur->next){
            temp = cur->next;
            cur->next = cur->next->next;
            temp->next = dummy_head->next;
            dummy_head->next = temp;
        }
        return dummy_head->next;
    }
};

2. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:


Input: 1->2
Output: false

Example 2:


Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

思路：链表比字符串难的地方就在于不能通过坐标来直接访问，而只能从头开始遍历到某个位置。那么根据回文串的特点，我们需要比较对应位置的值是否相等，那么我们首先需要找到链表的中点，这个可以用快慢指针来实现，我们使用快慢指针找中点的原理是fast和slow两个指针，每次快指针走两步，慢指针走一步，等快指针走完时，慢指针的位置就是中点。我们还需要用栈，每次慢指针走一步，都把值存入栈中，等到达中点时，链表的前半段都存入栈中了，由于栈的后进先出的性质，就可以和后半段链表按照回文对应的顺序比较了

这样做的时间是O(n)，空间也是O(n)


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        
        stack<int> s;
        ListNode *slow = head,*fast = head;
        s.push(head->val);
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
            s.push(slow->val);
        }
        // when the length is odd
        if(!fast->next) s.pop();
        
        while(slow->next){
            slow = slow->next;
            if(slow->val != s.top()) return false;
            s.pop();
        }
        return true;
    }
};

思路2：时间O(n)，空间O(1)的做法，使用快慢指针找到中点后，使用头插法，将后半部分链表倒置到最前


class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next) return true;
        
        ListNode *slow = head,*fast = head,*new_head = head,*mid = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
            mid = slow;
        }
        
        while(mid->next != NULL){
            slow = mid->next;
            mid->next = slow->next;
            slow->next = new_head;
            new_head = slow;
        }
        slow = head;
        cout << head->val <<endl;
        while(new_head != head){
            if(new_head->val != slow->val) return false;
            new_head = new_head->next;
            slow = slow->next;
        }
        return true;
    }
};

3.Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:


Input: 1->1->2
Output: 1->2

Example 2:


Input: 1->1->2->3->3
Output: 1->2->3


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* h = head;
        while(h){
            while(h->next && h->next->val == h->val){
                h->next = h->next->next;
            }
            h = h->next;
        }
        return head;
    }
};

4.Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:


Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:


Input: 1->1->1->2->3
Output: 2->3

思路：由于链表开头可能会有重复项，被删掉的话头指针会改变，而最终却还需要返回链表的头指针。所以需要定义一个新的节点，然后链上原链表，然后定义一个前驱指针和一个现指针，每当前驱指针指向新建的节点，现指针从下一个位置开始往下遍历，遇到相同的则继续往下，直到遇到不同项时，把前驱指针的next指向下面那个不同的元素。如果现指针遍历的第一个元素就不相同，则把前驱指针向下移一位。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode* pre = dummy_head,*cur;
        while(pre){
            cur = pre->next;
            if(cur && cur->next && cur->val == cur->next->val){
                while(cur && cur->next && cur->val == cur->next->val) cur = cur->next;
                pre->next = cur->next;
            }
            else pre = pre->next;
        }
        return dummy_head->next;
    }
};

5.Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:


Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

按照链表顺序往前即可，注意进位问题


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy_head = new ListNode(-1);
        ListNode* h1 = l1, *h2 = l2, *h3 = dummy_head;
        int remind = 0,res,num1,num2;
        while(h1 || h2){
            num1 = h1 ? h1->val:0;
            num2 = h2 ? h2->val:0;
            res = num1 + num2 + remind;
            remind = res/10;
            h3->next = new ListNode(res % 10);
            h3 = h3->next;
            if(h1) h1 = h1->next;
            if(h2) h2 = h2->next;
        }
        // 注意不要遗漏
        if(remind) h3->next = new ListNode(remind);
        return dummy_head->next;    
    }
};

二、mid

1.Reverse Linked List II

对于链表的问题，根据以往的经验一般都是要建一个dummy node，连上原链表的头结点，这样的话就算头结点变动了，我们还可以通过dummy->next来获得新链表的头结点。这道题的要求是只通过一次遍历完成，就拿题目中的例子来说，变换的是2,3,4这三个点，我们需要找到第一个开始变换结点的前一个结点，只要让pre向后走m-1步即可，故从1开始计数。万一是结点1开始变换的怎么办，这就是我们为啥要用dummy结点了，pre也可以指向dummy结点。然后就要开始交换了，由于一次只能交换两个结点，所以我们按如下的交换顺序：

1 -> 2 -> 3 -> 4 -> 5 -> NULL

1 -> 3 -> 2 -> 4 -> 5 -> NULL

1 -> 4 -> 3 -> 2 -> 5 -> NULL

注意这里直接跳过2，对3进行操作，2不跳过直接头插法会产生问题


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m == n || !head || !head->next) return head;
        
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode *pre = dummy_head,*cur,*temp;
        for(int i = 1;i < m;i++) pre = pre->next;
        // 注意这里往后移动一个，即从例子的3开始逆置，因为第一个在头插法里不需要去操作了！
        cur = pre->next;
        for(int i = m;i < n;i++){
            temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return dummy_head->next;
    }
};

2.Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

思路：第一步，将链表一分为二，用到快慢指针；第二步，反转第二部分，反转链表是很重要的根基；第三步，将两链表接起来。（这种题目要注意讨论奇数偶数的情况，注意两个都检验一遍）


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* slow = head,*fast = head,*mid,*temp;
        if(head == NULL || head->next == NULL || head->next->next == NULL) return;
        
        while(fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        // 头插法逆置后半段，这里mid最开始确实为终点，后来就不是了，实际中点为slow->next，mid是个遍历指针
        mid = slow->next;
        temp = mid->next;
        while(temp){
            mid->next = temp->next;
            temp->next = slow->next;
            slow->next = temp;
            temp = mid->next;
        }
        
        mid = slow->next;
        temp = head;
        // mid是奇数情况，temp->next != mid是偶数情况的终止条件
        while(mid && temp->next != mid){
            slow->next = mid->next;
            mid->next = temp->next;
            temp->next = mid;
            temp = mid->next;
            mid = slow->next; 
        }
    }
};

3.linked-list-cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:


Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

思路：快慢指针经典题（所有类型的分析：https://www.cnblogs.com/hiddenfox/p/3408931.html）

（没细看，也可以看看：http://www.cnblogs.com/wuyuegb2312/p/3183214.html）

设两个指针，一个每次走一步的慢指针和一个每次走两步的快指针，如果链表里有环的话，两个指针最终肯定会相遇。（为什么有环的情况下二者一定会相遇呢？因为fast先进入环，在slow进入之后，如果把slow看作在前面，fast在后面每次循环都向slow靠近1，所以一定会相遇，而不会出现fast直接跳过slow的情况）


/**
 * 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) {
        if(head == NULL || head->next == NULL) return false;
        
        ListNode *slow = head,*fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) return true;
        }
        return false;
    }
};

4.Linked List Cycle II

找到环的起始点

首先我们看下面这张图：

设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，第一次相遇之前，fast可能已经绕了好几圈，有 2（a + b） = a + b + n(b+c) ==> a = (n-1)(b+c) + c , where n>=1（这个结论很重要！）。

那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。


/**
 * 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) {
        if(!head || !head->next) return NULL;
        
        ListNode *slow = head,*fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            // 找到第一个重合的点Z
            if(slow == fast){
                // 一个指针从Z开始，一个指针从head开始，再次相遇找到Y
                fast = head;
                while(fast != slow){
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return NULL;
    }
};

5.Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note:Given n will always be valid.

思路：快慢指针经典用法


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *h1 = head,*h2 = head,*preh2;
        int count = 0;
        while(h1){
            count ++;
            h1 = h1->next;
            if(count > n){
                preh2 = h2; 
                h2 = h2->next;
            }
        }
        // 这里由于没有使用dummy head,使得n == 链表长度这种情况无法处理，必须单独处理
        if(count == n) return head->next;
        else if(count > n) preh2->next = h2->next;
        return head;
    }
};

使用dummy head的解法更加的清晰：


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode *h1 = dummy_head,*h2 = dummy_head;
        for(int i=0;i <= n;i++) h1 = h1->next;
        while(h1){
            h1 = h1->next;
            h2 = h2->next;
        }
        h2->next = h2->next->next;
        return dummy_head->next;
    }
};

6.Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:


Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:


Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
 
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

思路：快慢指针题，难度不大，注意对边界情况的考虑，首先一个就是当原链表为空时，直接返回NULL，还有就是当k大于链表长度和k远远大于链表长度时该如何处理，我们需要首先遍历一遍原链表得到链表长度n，然后k对n取余，这样k肯定小于n


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return head;
        
        ListNode *dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode* h = head,*slow = dummy_head,*fast = dummy_head;
        // 获取长度
        int length = 0;
        while(h){
            length ++;
            h = h->next;
        }
        k = k % length;
        // 快慢指针
        for(int i=0;i < k;i++) fast = fast->next;
        while(fast->next){
            fast = fast->next;
            slow = slow->next;
        }
        // 旋转
        fast->next = head;
        dummy_head->next = slow->next;
        slow->next = NULL;
        return dummy_head->next;
    }
};

7.Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

参考：https://blog.csdn.net/linhuanmars/article/details/22463599/

问题分析：这是一道链表操作的题目，要求复制一个链表，不过链表的每个结点带有一个随机指针，指向某一个结点。问题主要是在复制链表时，当我们访问一个结点时可能它的随机指针指向的结点还没有访问过，结点还没有创建，故不能直接复制

思路一：

我们先介绍一种比较直接的算法，思路是先按照复制一个正常链表的方式复制，复制的时候把复制的结点做一个HashMap，以旧结点为key，新节点为value。这么做的目的是为了第二遍扫描的时候我们按照这个哈希表把结点的随机指针接上。这个算法是比较容易想到的，总共要进行两次扫描，所以时间复杂度是O(2*n)=O(n)。空间上需要一个哈希表来做结点的映射，所以空间复杂度也是O(n)。


/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL) return NULL;
        map<RandomListNode *,RandomListNode *> m;
        RandomListNode *h = head;
        // 构造哈希表
        while(h){
            RandomListNode *new_node = new RandomListNode(h->label);
            m[h] = new_node;
            h = h->next;
        }
        h = head;
        // 复制
        while(h){
            m[h]->next = m[h->next];
            m[h]->random = m[h->random];
            h = h->next;
        }
        return m[head];
    }
};

思路二：

前面我们需要一个哈希表的原因是当我们访问一个结点时可能它的随机指针指向的结点还没有访问过，结点还没有创建，所以我们需要线性的额外空间。想避免使用额外空间，我们只能通过利用链表原来的数据结构来存储结点。

基本思路是这样的，对链表进行三次扫描，第一次扫描对每个结点进行复制，然后把复制出来的新节点接在原结点的next，也就是让链表变成一个重复链表，就是新旧更替；第二次扫描中我们把旧结点的随机指针赋给新节点的随机指针，因为新结点都跟在旧结点的下一个，所以赋值比较简单，就是node.next.random = node.random.next，其中node.next就是新结点，因为第一次扫描我们就是把新结点接在旧结点后面。现在我们把结点的随机指针都接好了，最后一次扫描我们把链表拆成两个，第一个还原原链表，而第二个就是我们要求的复制链表。因为现在链表是旧新更替，只要把每隔两个结点分别相连，对链表进行分割即可。这个方法总共进行三次线性扫描，所以时间复杂度是O(n)。而这里并不需要额外空间，所以空间复杂度是O(1)。比起上面的方法，这里多做一次线性扫描，但是不需要额外空间，还是比较值的。


/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL) return NULL;
        RandomListNode *h = head,*new_head,*h2;
        // (1)将新节点插入到原节点后面
        while(h){
            RandomListNode *new_node = new RandomListNode(h->label);
            new_node->next = h->next;
            h->next = new_node;
            h = new_node->next;
        }
        // (2)对新节点的random进行连接
        h = head;
        while(h){
            // 这里注意对h->random的检查，因为可能为NULL
            if(h->random) h->next->random = h->random->next;
            h = h->next->next;
        }
        // (3) 将链表拆开即可
        h = head;
        new_head = h->next;
        h2 = new_head;
        h->next = h->next->next;
        h = h->next;
        while(h){
            h2->next = h->next;
            h->next = h->next->next;
            h = h->next;
            h2 = h2->next;
        }
        return new_head;
    }
};

8.Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:


Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

思路：首先找到第一个大于或等于给定值的节点，用题目中给的例子来说就是先找到4，然后再找小于3的值，每找到一个就将其取出置于4之前即可


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode* pre,* precur;
        pre = dummy_head;
        precur = dummy_head;
        ListNode* cur = precur->next;
        // 找到第一个大于x的节点的前置节点，作为头
        while(cur && cur->val < x){
            precur = cur;
            pre = precur;
            cur = cur->next;
        }
        // 进行置换
        while(cur){
            if(cur->val < x){
                precur->next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
                pre = cur;
                cur = precur->next;
            }
            else{
                precur = precur->next;
                cur = cur->next;
            }
        }
        return dummy_head->next;
    }
};

思路二：将所有小于给定值的节点取出组成一个新的链表，此时原链表中剩余的节点的值都大于或等于给定值，只要将原链表直接接在新链表后即可


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummy_head = new ListNode(-1);
        ListNode* small_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode* cur = dummy_head,*temp;
        ListNode* small_tail = small_head;
        while(cur){
            // 插入到小的那个链表中
            if(cur->next && cur->next->val < x){
                temp = cur->next;
                cur->next = cur->next->next;
                temp->next = small_tail->next;
                small_tail->next = temp;
                small_tail = temp;
            }
            else cur = cur->next;
        }
        small_tail->next = dummy_head->next;
        return small_head->next;
    }
};

9.Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

思路：我们可以使用两个指针来做，odd指向奇节点，cur指向偶节点，然后把偶节点cur后面的那个奇节点提前到odd的后面，然后odd和cur各自前进一步，此时cur又指向偶节点，odd指向当前奇节点的末尾


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* odd_head = new ListNode(-1);
        ListNode* dummy_head = new ListNode(-1);
        dummy_head->next = head;
        ListNode* odd = odd_head,*cur = dummy_head,*temp;
        while(cur && cur->next){
            temp = cur->next;
            cur->next = cur->next->next;
            odd->next = temp;
            odd = temp;
            cur = cur->next;
        }
        odd->next = dummy_head->next;
        return odd_head->next;
    }
};

三、hard

1.LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:


LRUCache cache = new LRUCache( 2 /* capacity */ );
 
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

思路：

LRUCache是一种常用的缓存替换算法，其原理是根据使用率淘汰数据，一般会实现为一个队列，如果一个cache命中，则将这个数据移动到队列的头部，这样，不经常使用的cache就会逐渐移向队列尾部，当cache容量满时，就从队列尾部取出一个数据丢掉。总的来说，涉及到了数据在头部插入、尾部移除、随机取出数据这样几个主要的操作，所以双向链表是一个不错的选择。但是我们再考虑到这样一个问题：如果直接使用LinkedList，从Cache中取数据时每次都要遍历队列，无谓的消耗了大量时间，所以我们自然而然的加上了HashMap，HashMap中存储了指向LinkedList的指针，这样就可以保证在O(1)的访问复杂度。

参考：https://www.jianshu.com/p/61e7c853aaa6

https://blog.csdn.net/zsjmfy/article/details/53404608（java）


struct Node{
public:
    // 此处为实例化，使得可以以Node head = new Node(-1,-1)的形式初始化
    Node(int k,int v):key(k),val(v) {}
    int key;
    int val;
    Node * pre;
    Node * next;
};
 
class LRUCache {
public:    
    LRUCache(int capacity) {
        // 这里注意，这些变量已经在外部初始化了，这里不要再重新初始化，不然会有问题
        _size = capacity;
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        // 这两句不要忘了，使得其首尾相连
        head->next = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        if(m.find(key) == m.end()){
            return -1;
        }
        else{
            Node *node_now = m[key];
            node_now->next->pre = node_now->pre;
            node_now->pre->next= node_now->next;
            move_to_tail(node_now);
            return m[key]->val;
        }
    }
    
    void put(int key, int value) {
        if(get(key) != -1){
            Node *node_now = m[key];
            node_now->val = value;
            node_now->pre->next = node_now->next;
            node_now->next->pre = node_now->pre;
            move_to_tail(node_now);
            return;
        }
        else if(_size == m.size()){
            m.erase(head->next->key);
            head->next = head->next->next;
            head->next->pre = head;  
        }
        Node *node_now = new Node(key,value);
        move_to_tail(node_now);
        m[key] = node_now;
    }
 
// 下面这些是需要在类内全局访问的，所以在外部初始化，设置为public的话，类外也可以初始化    
private:
    map<int,Node *> m;
    int _size;
    // 这里开始用了Node head的形式，但是会导致head.next这是一个指针，访问它的next必须写成
    //head.next->next，特别凌乱，而且不能写成head->next->next 
    Node *head;
    Node *tail;
    
void move_to_tail(Node * n){
    n->pre = tail->pre;
    n->pre->next = n;
    n->next = tail;
    tail->pre = n; 
}
    
};
 
// *
//  * 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);

2.Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example: Given 1->2->3->4, you should return the list as 2->1->4->3


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* h = head,*pretail,*temp;
        // 加入虚拟的头
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        pretail = dummy;
        while(h && h->next){
            // 头插法
            temp = h->next;
            h->next = h->next->next;
            pretail->next = temp;
            temp->next = h;
            
            pretail = h;
            h = h->next;      
        }
        return dummy->next;
    }
};

3.Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

思路：注意未满k的部分不逆置

这题看起来简单，结果我一直出问题。。。感觉链表里需要重点理清楚怎么逆置

关于头插法可参考：https://blog.csdn.net/yyw_lucky3/article/details/64923059


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *h = head,*lasttail,*curhead,*curtail,*nexthead,*temp;
        // 设置一个空节点，在head前
        ListNode *prehead = new ListNode(0);
        prehead->next = head;
        //初始化
        lasttail = prehead;
        curhead = head;
        int count = 1;
        while(h){
            h = h->next;
            count ++;
            if(count == k && h){
                curtail = h;
                nexthead = h->next;
                h = h->next;
                while(curhead->next != nexthead){
                    // 标准头插法，所以需要前面的那个prehead
                    temp = curhead->next;
                    curhead->next = curhead->next->next;
                    temp->next = lasttail->next;
                    lasttail->next = temp;
                }
                count = 1;
                lasttail = curhead;
                curhead = nexthead;
            }
        }
        return prehead->next;
    }
};

别的博主的写法，其中的解法一更加简洁：https://www.cnblogs.com/grandyang/p/4441324.html


 
-1->1->2->3->4->5
 |           |
pre         next
 
-1->3->2->1->4->5
          |  |
         pre next


class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (!head || k == 1) return head;
        ListNode *dummy = new ListNode(-1);
        ListNode *pre = dummy, *cur = head;
        dummy->next = head;
        int i = 0;
        while (cur) {
            ++i;
            if (i % k == 0) {
                pre = reverseOneGroup(pre, cur->next);
                cur = pre->next;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
 
    ListNode *reverseOneGroup(ListNode *pre, ListNode *next) {
        ListNode *last = pre->next;
        ListNode *cur = last->next;
        while(cur != next) {
            last->next = cur->next;
            cur->next = pre->next;
            pre->next = cur;
            cur = last->next;
        }
        return last;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/395393