链表中等题（下）
class Solution {
public:
// 递归
Node *generate(Node *head) {
if (head == nullptr) return nullptr;
// 把后面的扁平化
Node *next = generate(head->next);
// 把孩子扁平化
Node *child = generate(head->child);
if (child != nullptr) {
// 把child接到head和head.next之间
head->child = nullptr;
head->next = child;
child->prev = head;
if (next != nullptr) {
Node *cur = child;
// cur移到扁平化后的child的尾节点
while (cur->next != nullptr) {
cur = cur->next;
}
// 把next接到child的尾节点后
cur->next = next;
next->prev = cur;
}
}
return head;
}
Node *flatten(Node *head) {
return generate(head);
}
};
// todo 迭代
// todo
struct ListNode *detectCycle(struct ListNode *head) {
// 环外节点数a 环内节点数b
// 快慢指针经过的节点个数关系: f = 2s
// 相遇时: f = s + n*b -> s = n*b, f = 2*n*b
// 走到入口节点经过的节点个数k = a + n*b, 先前进a步到入口节点, 然后在环里转圈
// f = 0, s = n*b -> f = a, s = a + n*b相遇在入口节点
struct ListNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 首次相遇时，slow已经跑了b步，只需跑a步就能到达入口
// fast返回开头head节点，也只需跑a步就能到达入口
// 此时a是几并不知道，但是可以确定的是，slow和fast都在跑a步就会在入口相遇
if (slow == fast) {
fast = head;
// 此时f = 0, s = 1*b
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
// 结束时f = a, s = a + 1*b
return slow;
}
}
return NULL;
}
// 删除中偏右的节点
struct ListNode *deleteMiddle(struct ListNode *head) {
if (head->next == NULL)return NULL;
struct ListNode *slow = head, *fast = head, *pre = NULL;
// 先把slow指向中偏右的节点，此时pre指向的就是slow前面的一个节点
while (fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = pre->next->next;
return head;
}
// 反转链表
struct ListNode *reverse(struct ListNode *head) {
struct ListNode *pre = NULL, *next, *cur = head;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
struct ListNode *doubleIt(struct ListNode *head) {
// 进位
int carry = 0;
// 反转后从低位开始处理
struct ListNode *newHead = reverse(head);
struct ListNode *cur = newHead;
while (cur != NULL) {
int val = (2 * cur->val + carry) % 10;
carry = (2 * cur->val + carry) / 10;
cur->val = val;
cur = cur->next;
}
// 多出来一个最高位
if (carry != 0) {
struct ListNode *node = (struct ListNode *) malloc(sizeof(struct ListNode));
node->val = carry;
node->next = reverse(newHead);
return node;
}
return reverse(newHead);
}
// 当前位是否会由于后面一位的翻倍而导致要加上进位，取决于后面一位是否大于4
struct ListNode *doubleIt(struct ListNode *head) {
struct ListNode *res = head;
if (head->val > 4) {
struct ListNode *node = (struct ListNode *) malloc(sizeof(struct ListNode));
node->val = 1;
node->next = head;
res = node;
}
// 从原链表的开头开始
struct ListNode *cur = head;
while (cur != NULL) {
cur->val = (cur->val * 2) % 10;
// 是否要加上进位
if (cur->next != NULL && cur->next->val > 4) cur->val++;
cur = cur->next;
}
return res;
}
int *nodesBetweenCriticalPoints(struct ListNode *head, int *returnSize) {
*returnSize = 2;
int *res = (int *) calloc(2, sizeof(int));
// 只有两个节点直接返回
if (head->next->next == NULL) {
res[0] = -1;
res[1] = -1;
return res;
}
// 前驱的值
int preVal = head->val;
// 当前节点
struct ListNode *cur = head->next;
// 第一个极值点的下标，也是最小的下标，用于计算最远距离
int minIndex = -1;
// 上一个极值点的下标，用于跟新最近距离
int preIndex = -1;
// 当前节点的下标
int curIndex = 1;
// 极值点之间最小距离
int min = 0x7fffffff;
// 从第二个节点遍历到倒数第二个节点
while (cur->next != NULL) {
// cur是极值点
if ((cur->val > preVal && cur->val > cur->next->val)
|| (cur->val < preVal && cur->val < cur->next->val)) {
if (minIndex == -1)
minIndex = curIndex;
else if (curIndex - preIndex < min)
// 更新最小距离
min = curIndex - preIndex;
preIndex = curIndex;
}
preVal = cur->val;
curIndex++;
cur = cur->next;
}
// 只有一个极值点或者一个都没有
if (preIndex == minIndex) {
res[0] = -1;
res[1] = -1;
} else {
res[0] = min;
// 最远距离就是最后一个极值点的位置减去第一个极值点的位置
res[1] = preIndex - minIndex;
}
return res;
}
// todo 数组模拟循环队列、循环单链表、循环双链表
struct ListNode *reverseBetween(struct ListNode *head, int left, int right) {
if (head == NULL || head->next == NULL || left >= right) return head;
// 虚拟头节点
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode *preNode = dummyHead;
int count = left - 1;
// preNode为left的直接前驱
while (count-- > 0) preNode = preNode->next;
// 暂存反转后的子链表的尾节点
struct ListNode *newTail = preNode->next;
// 反转子链表
struct ListNode *pre = NULL, *next = NULL, *cur = preNode->next;
count = right - left + 1;
while (count-- > 0) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
// pre是right节点，即反转后子链表的头节点，next是原链表中right的直接后继
preNode->next = pre;
newTail->next = next;
return dummyHead->next;
}
// 测试用例通过了，但耗时太长。应该是慢在了lRUCacheGet时对节点的定位
struct MyListNode {
int key;
int val;
struct MyListNode *prev;
struct MyListNode *next;
};
// 带头尾节点的双向链表
typedef struct {
struct MyListNode *dummyHead;
struct MyListNode *dummyTail;
int len;
int maxLen;
} LRUCache;
LRUCache *lRUCacheCreate(int capacity) {
LRUCache *cache = (LRUCache *) malloc(sizeof(LRUCache));
cache->dummyHead = (struct MyListNode *) malloc(sizeof(struct MyListNode));
cache->dummyTail = (struct MyListNode *) malloc(sizeof(struct MyListNode));
cache->dummyHead->prev = NULL;
cache->dummyHead->next = cache->dummyTail;
cache->dummyTail->prev = cache->dummyHead;
cache->dummyTail->next = NULL;
cache->len = 0;
cache->maxLen = capacity;
return cache;
}
// 接到dummyHead的后面
void addToHead(struct MyListNode *dummyHead, struct MyListNode *node) {
node->next = dummyHead->next;
node->prev = dummyHead;
node->next->prev = node;
dummyHead->next = node;
}
// 把节点移到开头
void moveToHead(struct MyListNode *dummyHead, struct MyListNode *node) {
// 把node从中间取出来
node->prev->next = node->next;
node->next->prev = node->prev;
// 接到dummyHead的后面
addToHead(dummyHead, node);
}
// 找到key对应的节点
struct MyListNode *findNode(LRUCache *obj, int key) {
struct MyListNode *cur = obj->dummyHead->next;
while (cur != obj->dummyTail) {
if (cur->key == key) return cur;
cur = cur->next;
}
return NULL;
}
int lRUCacheGet(LRUCache *obj, int key) {
struct MyListNode *node = findNode(obj, key);
if (node == NULL) return -1;
// 刚访问过的节点要移动到开头
moveToHead(obj->dummyHead, node);
return node->val;
}
void lRUCachePut(LRUCache *obj, int key, int value) {
// 如果key已存在，修改value，然后移到开头就行
struct MyListNode *find = findNode(obj, key);
if (find != NULL) {
find->val = value;
moveToHead(obj->dummyHead, find);
return;
}
// 不存在，则只能插入
if (obj->len < obj->maxLen) {
struct MyListNode *node = (struct MyListNode *) malloc(sizeof(struct MyListNode));
node->key = key;
node->val = value;
addToHead(obj->dummyHead, node);
// 加入第一个节点时，要把虚拟尾节点的前驱指针指向当前节点
if (obj->len == 0) obj->dummyTail->prev = node;
obj->len++;
} else {
// 缓存已满，淘汰最近最久未访问的节点，也就是尾节点
// 直接把新的值覆盖到尾节点中，再把尾节点移到开头
struct MyListNode *tail = obj->dummyTail->prev;
tail->key = key;
tail->val = value;
moveToHead(obj->dummyHead, tail);
}
}
void lRUCacheFree(LRUCache *obj) {
free(obj);
obj = NULL;
}
// 用hashMap定位节点
class LRUCache {
ListNode dummyHead;
ListNode dummyTail;
int capacity;
Map<Integer, ListNode> map;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
dummyHead = new ListNode();
dummyTail = new ListNode();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
ListNode node = map.get(key);
moveToHead(node);
return node.value;
}
public void addToHead(ListNode node) {
map.put(node.key, node);
node.next = dummyHead.next;
dummyHead.next.prev = node;
dummyHead.next = node;
node.prev = dummyHead;
}
public void moveToHead(ListNode node) {
// 断开
node.prev.next = node.next;
node.next.prev = node.prev;
// 接上
node.next = dummyHead.next;
dummyHead.next.prev = node;
node.prev = dummyHead;
dummyHead.next = node;
}
public void deleteNode(ListNode node) {
map.remove(node.key);
node.prev.next = node.next;
node.next.prev = node.prev;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
ListNode node = map.get(key);
node.value = value;
moveToHead(node);
return;
}
if (map.size() == capacity) deleteNode(dummyTail.prev);
ListNode node = new ListNode(key, value);
addToHead(node);
}
}
class ListNode {
int key;
int value;
ListNode prev;
ListNode next;
public ListNode(int key, int value, ListNode prev, ListNode next) {
this.key = key;
this.value = value;
this.prev = prev;
this.next = next;
}
public ListNode(int key, int value) {
this.key = key;
this.value = value;
}
public ListNode() {
}
}
// 数组模拟循环双端队列（测试用例通过了，但耗时太长。）
struct MyNode {
int key;
int val;
};
typedef struct {
struct MyNode *queue;
int front;
int rear;
int size;
} LRUCache;
LRUCache *lRUCacheCreate(int capacity) {
LRUCache *cache = (LRUCache *) malloc(sizeof(LRUCache));
// 多留一位
cache->size = capacity + 1;
cache->front = 0;
cache->rear = 0;
cache->queue = (struct MyNode *) calloc(capacity + 1, sizeof(struct MyNode));
return cache;
}
int getLen(LRUCache *obj) {
return (obj->rear - obj->front + obj->size) % obj->size;
}
bool isFull(LRUCache *obj) {
return getLen(obj) == obj->size - 1;
}
void addToHead(LRUCache *obj, int key, int value) {
obj->front = (obj->front - 1 + obj->size) % obj->size;
obj->queue[obj->front].key = key;
obj->queue[obj->front].val = value;
}
void moveToHead(LRUCache *obj, int index) {
obj->front = (obj->front - 1 + obj->size) % obj->size;
obj->queue[obj->front].key = obj->queue[index].key;
obj->queue[obj->front].val = obj->queue[index].val;
while (index != obj->rear) {
// 后一个节点往前移动一格
obj->queue[index].key = obj->queue[(index + 1) % obj->size].key;
obj->queue[index].val = obj->queue[(index + 1) % obj->size].val;
index = (index + 1 + obj->size) % obj->size;
}
obj->rear = (obj->rear - 1 + obj->size) % obj->size;
}
int findNodeIndex(LRUCache *obj, int key) {
int count = getLen(obj);
int index = obj->front;
while (count-- > 0) {
if (obj->queue[index].key == key) return index;
index = (index + 1 + obj->size) % obj->size;
}
return -1;
}
int lRUCacheGet(LRUCache *obj, int key) {
int index = findNodeIndex(obj, key);
if (index == -1) return -1;
int res = obj->queue[index].val;
moveToHead(obj, index);
return res;
}
void lRUCachePut(LRUCache *obj, int key, int value) {
// 若已有就修改并移到开头
int index = findNodeIndex(obj, key);
if (index != -1) {
obj->queue[index].val = value;
moveToHead(obj, index);
return;
}
// 满了就要先移除末尾元素
if (isFull(obj)) {
obj->rear = (obj->rear - 1 + obj->size) % obj->size;
}
// 加到开头
addToHead(obj, key, value);
}
void lRUCacheFree(LRUCache *obj) {
free(obj);
obj = NULL;
}
// 加了散列，依旧正确但超时
struct MyNode {
int key;
int val;
};
typedef struct {
struct MyNode *queue;
int front;
int rear;
int size;
int *hashMap;
} LRUCache;
LRUCache *lRUCacheCreate(int capacity) {
LRUCache *cache = (LRUCache *) malloc(sizeof(LRUCache));
// 多留一位
cache->size = capacity + 1;
cache->front = 0;
cache->rear = 0;
cache->queue = (struct MyNode *) calloc(capacity + 1, sizeof(struct MyNode));
// 下标对应key，值对应节点再queue中的下标
cache->hashMap = (int *) malloc(sizeof(int) * 6000);
for (int i = 0; i < 6000; ++i) {
cache->hashMap[i] = -1;
}
return cache;
}
int getLen(LRUCache *obj) {
return (obj->rear - obj->front + obj->size) % obj->size;
}
bool isFull(LRUCache *obj) {
return getLen(obj) == obj->size - 1;
}
void addToHead(LRUCache *obj, int key, int value) {
obj->front = (obj->front - 1 + obj->size) % obj->size;
obj->queue[obj->front].key = key;
obj->queue[obj->front].val = value;
obj->hashMap[key] = obj->front;
}
void moveToHead(LRUCache *obj, int index) {
obj->front = (obj->front - 1 + obj->size) % obj->size;
obj->queue[obj->front].key = obj->queue[index].key;
obj->queue[obj->front].val = obj->queue[index].val;
obj->hashMap[obj->queue[obj->front].key] = obj->front;
// 要往前搬动的元素个数
int count = (obj->rear - index + obj->size) % obj->size - 1;
while (count-- > 0) {
// 后一个节点往前移动一格
obj->queue[index].key = obj->queue[(index + 1) % obj->size].key;
obj->queue[index].val = obj->queue[(index + 1) % obj->size].val;
obj->hashMap[obj->queue[index].key] = index;
index = (index + 1 + obj->size) % obj->size;
}
obj->rear = (obj->rear - 1 + obj->size) % obj->size;
// 淘汰末尾元素， obj->hashMap[obj->queue[obj->rear].key] == obj->rear表示这个key不仅有效而且没有移动位置，可以直接删掉了
// 不等时，这个元素可能是被移到前面去了，所以不用更新hashMap，否则就覆盖掉之前的移动了
if (obj->hashMap[obj->queue[obj->rear].key] == obj->rear) obj->hashMap[obj->queue[obj->rear].key] = -1;
}
int findNodeIndex(LRUCache *obj, int key) {
return obj->hashMap[key];
}
int lRUCacheGet(LRUCache *obj, int key) {
int index = findNodeIndex(obj, key);
if (index == -1) return -1;
int res = obj->queue[index].val;
moveToHead(obj, index);
return res;
}
void lRUCachePut(LRUCache *obj, int key, int value) {
// 若已有就修改并移到开头
int index = findNodeIndex(obj, key);
if (index != -1) {
obj->queue[index].val = value;
moveToHead(obj, index);
return;
}
// 满了就要先移除末尾元素
if (isFull(obj)) {
obj->rear = (obj->rear - 1 + obj->size) % obj->size;
if (obj->hashMap[obj->queue[obj->rear].key] == obj->rear) obj->hashMap[obj->queue[obj->rear].key] = -1;
}
// 加到开头
addToHead(obj, key, value);
}
void lRUCacheFree(LRUCache *obj) {
free(obj);
obj = NULL;
}
struct ListNode *removeNthFromEnd(struct ListNode *head, int n) {
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode *slow = dummyHead, *fast = dummyHead;
int count = n + 1;
while (count-- > 0) fast = fast->next;
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummyHead->next;
}
struct ListNode *deleteDuplicates(struct ListNode *head) {
if (head == NULL || head->next == NULL) return head;
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = head;
// pre始终指向不重复的元素的最后一个
struct ListNode *pre = dummyHead, *cur = head;
while (cur != NULL) {
// 是否出现重复
bool flag = false;
while (cur->next != NULL && cur->next->val == cur->val) {
flag = true;
cur = cur->next;
}
if (flag) {
// 有重复时，cur指向重复的元素的最后一个，跳过这些重复元素
pre->next = cur->next;
// pre指针不动，因为后面还有可能有重复的
} else {
// cur不是重复元素，pre可以指向cur了
pre = cur;
}
cur = cur->next;
}
return dummyHead->next;
}
// 先遍历一遍统计元素出现次数，再次遍历删掉多次出现的元素
// 递归
struct ListNode *deleteDuplicates(struct ListNode *head) {
if (head == NULL || head->next == NULL) return head;
struct ListNode *cur = head;
bool flag = false;
while (cur->next != NULL && cur->next->val == head->val) {
flag = true;
cur = cur->next;
}
// 循环结束时，cur->next为空或者是个不同于head->val的节点
if (flag) {
// head到cur的节点全是相同的，都跳过
return deleteDuplicates(cur->next);
} else {
head->next = deleteDuplicates(head->next);
return head;
}
}
struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = NULL;
struct ListNode *pre = dummyHead;
// 进位
int carry = 0;
while (l1 != NULL && l2 != NULL) {
struct ListNode *node = (struct ListNode *) malloc(sizeof(struct ListNode));
node->val = (l1->val + l2->val + carry) % 10;
node->next = NULL;
carry = (l1->val + l2->val + carry) / 10;
pre->next = node;
pre = pre->next;
l1 = l1->next;
l2 = l2->next;
}
while (l1 != NULL) {
int val = l1->val + carry;
l1->val = val % 10;
carry = val / 10;
pre->next = l1;
pre = pre->next;
l1 = l1->next;
}
while (l2 != NULL) {
int val = l2->val + carry;
l2->val = val % 10;
carry = val / 10;
pre->next = l2;
pre = pre->next;
l2 = l2->next;
}
if (carry != 0) {
struct ListNode *node = (struct ListNode *) malloc(sizeof(struct ListNode));
node->val = carry;
node->next = NULL;
pre->next = node;
}
return dummyHead->next;
}
struct ListNode *reverseBetween(struct ListNode *head, int left, int right) {
if (head == NULL || head->next == NULL || left >= right) return head;
// 虚拟头节点
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode *preNode = dummyHead;
int count = left - 1;
// preNode为left的直接前驱
while (count-- > 0) preNode = preNode->next;
// 暂存反转后的子链表的尾节点
struct ListNode *newTail = preNode->next;
// 反转子链表
struct ListNode *pre = NULL, *next = NULL, *cur = preNode->next;
count = right - left + 1;
while (count-- > 0) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
// pre是right节点，即反转后子链表的头节点，next是原链表中right的直接后继
preNode->next = pre;
newTail->next = next;
return dummyHead->next;
}
struct ListNode *rotateRight(struct ListNode *head, int k) {
if(head == NULL || head->next == NULL) return head;
struct ListNode *cur = head;
int len = 0;
while (cur != NULL) {
len++;
cur = cur->next;
}
k %= len;
if(k == 0) return head;
// 三次反转
head = reverseBetween(head, 1, len);
head = reverseBetween(head, 1, k);
head = reverseBetween(head, k + 1, len);
return head;
}
// 把后面的链表移到前面
struct ListNode *rotateRight(struct ListNode *head, int k) {
if (head == NULL || head->next == NULL) return head;
struct ListNode *cur = head;
int len = 0;
while (cur != NULL) {
len++;
cur = cur->next;
}
k %= len;
if (k == 0) return head;
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode *slow = head;
struct ListNode *fast = head;
while (k-- > 0) fast = fast->next;
while (fast->next != NULL) {
slow = slow->next;
fast = fast->next;
}
// 把slow后面的链表移到链表前面
fast->next = dummyHead->next;
dummyHead->next = slow->next;
// slow变成新的尾节点
slow->next = NULL;
return dummyHead->next;
}