刷完了Leetcode所有的链表简单—中等题，归纳一下用过的技巧。
一、快慢指针
相位差快慢
例题：实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode* fast = head, *slow = head;
for(int i = 0; i < k - 1; i++)
{
fast = fast->next;
}
while(fast->next != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow->val;
}
};- class Solution {
- public:
- int kthToLast(ListNode* head, int k) {
- ListNode* fast = head, *slow = head;
- for(int i = 0; i < k - 1; i++)
- {
- fast = fast->next;
- }
- while(fast->next != NULL)
- {
- fast = fast->next;
- slow = slow->next;
- }
- return slow->val;
- }
- };
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode* fast = head, *slow = head;
for(int i = 0; i < k - 1; i++)
{
fast = fast->next;
}
while(fast->next != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow->val;
}
};先让快指针走k-1步，再让快慢指针同速度前进。当快指针走到尾部，慢指针自然在倒数第k个节点。
步长快慢
例题：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
class Solution {
public:
ListNode* middleNode(ListNode* head) {
if(head == NULL)
{
return NULL;
}
ListNode* fast = head;
ListNode* low = head;
while(fast->next != NULL)
{
low = low->next;
fast = fast->next->next;
if(fast == NULL)
{
break;
}
}
return low;
}
};- class Solution {
- public:
- ListNode* middleNode(ListNode* head) {
- if(head == NULL)
- {
- return NULL;
- }
- ListNode* fast = head;
- ListNode* low = head;
- while(fast->next != NULL)
- {
- low = low->next;
- fast = fast->next->next;
- if(fast == NULL)
- {
- break;
- }
- }
- return low;
- }
- };
class Solution {
public:
ListNode* middleNode(ListNode* head) {
if(head == NULL)
{
return NULL;
}
ListNode* fast = head;
ListNode* low = head;
while(fast->next != NULL)
{
low = low->next;
fast = fast->next->next;
if(fast == NULL)
{
break;
}
}
return low;
}
};让快慢指针同时从头指针出发，快指针一次走两步，慢指针一次走一步，当快指针到达尾部，慢指针自然在正中间。
二、缓冲区
也就是另外建立存储数据的区域，例题：编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
class Solution {
public:
ListNode* removeDuplicateNodes(ListNode* head) {
ListNode* cur = head, *prev;
int data[20001] = {0};
while(cur != NULL)
{
if(data[cur->val] == 0)
{
data[cur->val]++;
prev = cur;
cur = cur->next;
}
else if(data[cur->val] == 1)
{
prev->next = cur->next;
delete cur;
cur = prev->next;
}
}
return head;
}
};- class Solution {
- public:
- ListNode* removeDuplicateNodes(ListNode* head) {
- ListNode* cur = head, *prev;
- int data[20001] = {0};
- while(cur != NULL)
- {
- if(data[cur->val] == 0)
- {
- data[cur->val]++;
- prev = cur;
- cur = cur->next;
- }
- else if(data[cur->val] == 1)
- {
- prev->next = cur->next;
- delete cur;
- cur = prev->next;
- }
- }
- return head;
- }
- };
class Solution {
public:
ListNode* removeDuplicateNodes(ListNode* head) {
ListNode* cur = head, *prev;
int data[20001] = {0};
while(cur != NULL)
{
if(data[cur->val] == 0)
{
data[cur->val]++;
prev = cur;
cur = cur->next;
}
else if(data[cur->val] == 1)
{
prev->next = cur->next;
delete cur;
cur = prev->next;
}
}
return head;
}
};这里将每个数据放入对应的桶中，如果桶中已经有数据，自然判断出重复。
三、使用STL
同样也是使用了缓冲区，不过stl的一些方法可以大大简便操作
使用vector
例题：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
class Solution {
public:
void reorderList(ListNode* head) {
if (!head) return;
vector<ListNode*> vec;
ListNode* cur = head;
while (cur) {
vec.push_back(cur);
cur = cur->next;
}
int left = 0;
int right = vec.size() - 1;
while (left < right) {
vec[left]->next = vec[right];
vec[right--]->next = vec[++left];
}
vec[left]->next = nullptr;
}
};- class Solution {
- public:
- void reorderList(ListNode* head) {
- if (!head) return;
- vector<ListNode*> vec;
- ListNode* cur = head;
- while (cur) {
- vec.push_back(cur);
- cur = cur->next;
- }
- int left = 0;
- int right = vec.size() - 1;
- while (left < right) {
- vec[left]->next = vec[right];
- vec[right--]->next = vec[++left];
- }
- vec[left]->next = nullptr;
- }
- };
class Solution {
public:
void reorderList(ListNode* head) {
if (!head) return;
vector<ListNode*> vec;
ListNode* cur = head;
while (cur) {
vec.push_back(cur);
cur = cur->next;
}
int left = 0;
int right = vec.size() - 1;
while (left < right) {
vec[left]->next = vec[right];
vec[right--]->next = vec[++left];
}
vec[left]->next = nullptr;
}
};vector简便了取未操作过的首、尾节点的方法
使用stack
例题：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构。给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
class Solution {
public:
Node* flatten(Node* head) {
if (!head) return head;
stack<Node*> n;
Node* p = head, *temp;
while (true)
{
while(true)
{
if (p->child)
{
if (p->next)
n.push(p->next);
p->next = p->child;
p->next->prev = p;
p->child = NULL;
}
if(!(p->next))
break;
p = p->next;
}
if (n.empty())
break;
temp = p;
p = n.top();
n.pop();
temp->next = p;
p->prev = temp;
}
return head;
}
};- class Solution {
- public:
- Node* flatten(Node* head) {
- if (!head) return head;
- stack<Node*> n;
- Node* p = head, *temp;
- while (true)
- {
- while(true)
- {
- if (p->child)
- {
- if (p->next)
- n.push(p->next);
- p->next = p->child;
- p->next->prev = p;
- p->child = NULL;
- }
- if(!(p->next))
- break;
- p = p->next;
- }
- if (n.empty())
- break;
- temp = p;
- p = n.top();
- n.pop();
- temp->next = p;
- p->prev = temp;
- }
- return head;
- }
- };
class Solution {
public:
Node* flatten(Node* head) {
if (!head) return head;
stack<Node*> n;
Node* p = head, *temp;
while (true)
{
while(true)
{
if (p->child)
{
if (p->next)
n.push(p->next);
p->next = p->child;
p->next->prev = p;
p->child = NULL;
}
if(!(p->next))
break;
p = p->next;
}
if (n.empty())
break;
temp = p;
p = n.top();
n.pop();
temp->next = p;
p->prev = temp;
}
return head;
}
};使用了stack保证了后进先出，使得扁平化从最分支到主枝进行。
使用map
map确保了键值对的唯一性，可以快速解决重复值问题。例题：给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
map<int, ListNode*> map;
int sum = 0;
ListNode* dummy = new ListNode(0), *cur = dummy;
dummy->next = head;
while (cur)
{
sum += cur->val;
map[sum] = cur;
cur = cur->next;
}
for(cur = dummy, sum = 0; cur; cur = cur->next)
{
sum += cur->val;
if (map.find(sum) != map.end())
cur->next = map[sum]->next;
}
return dummy->next;
}
};- class Solution {
- public:
- ListNode* removeZeroSumSublists(ListNode* head) {
- map<int, ListNode*> map;
- int sum = 0;
- ListNode* dummy = new ListNode(0), *cur = dummy;
- dummy->next = head;
- while (cur)
- {
- sum += cur->val;
- map[sum] = cur;
- cur = cur->next;
- }
- for(cur = dummy, sum = 0; cur; cur = cur->next)
- {
- sum += cur->val;
- if (map.find(sum) != map.end())
- cur->next = map[sum]->next;
- }
- return dummy->next;
- }
- };
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
map<int, ListNode*> map;
int sum = 0;
ListNode* dummy = new ListNode(0), *cur = dummy;
dummy->next = head;
while (cur)
{
sum += cur->val;
map[sum] = cur;
cur = cur->next;
}
for(cur = dummy, sum = 0; cur; cur = cur->next)
{
sum += cur->val;
if (map.find(sum) != map.end())
cur->next = map[sum]->next;
}
return dummy->next;
}
};从头开始计算每到达一个节点时，前面所有节点值的总和，并且存在map中，如果有一个序列和为0，那么必有两个总和相等。再一次遍历时，如果某个总和在map中但不是当前节点，那么map中对应的节点和当前节点之间的和必定是0.
四、递归
链表的节点是相似的，可以使用递归解决。例题：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(!head) return NULL;
if(head->val == val) return head->next;
head->next = deleteNode(head->next,val);
return head;
}
};- class Solution {
- public:
- ListNode* deleteNode(ListNode* head, int val) {
- if(!head) return NULL;
- if(head->val == val) return head->next;
- head->next = deleteNode(head->next,val);
- return head;
- }
- };
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(!head) return NULL;
if(head->val == val) return head->next;
head->next = deleteNode(head->next,val);
return head;
}
};通过递归，从头结点开始，下一个节点等于删除的只便跳过，重新连接链表。
五、补齐链表
当操作的两个链表长度不等时，可以先补齐至相同长度再操作。
例题：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。
void addLinkList(struct ListNode* l1, struct ListNode* l2,int *cout)
{
if(l1==NULL||l2==NULL)
return;
if(l1->next!=NULL&&l2->next!=NULL)
addLinkList(l1->next,l2->next,cout);
int Sum=l1->val+l2->val+*cout;
if(Sum>=10)
{
*cout=1;
l1->val=Sum%10;
}
else
{
*cout=0;
l1->val=Sum;
}
return;
}- void addLinkList(struct ListNode* l1, struct ListNode* l2,int *cout)
- {
- if(l1==NULL||l2==NULL)
- return;
- if(l1->next!=NULL&&l2->next!=NULL)
- addLinkList(l1->next,l2->next,cout);
- int Sum=l1->val+l2->val+*cout;
- if(Sum>=10)
- {
- *cout=1;
- l1->val=Sum%10;
- }
- else
- {
- *cout=0;
- l1->val=Sum;
- }
- return;
- }
void addLinkList(struct ListNode* l1, struct ListNode* l2,int *cout)
{
if(l1==NULL||l2==NULL)
return;
if(l1->next!=NULL&&l2->next!=NULL)
addLinkList(l1->next,l2->next,cout);
int Sum=l1->val+l2->val+*cout;
if(Sum>=10)
{
*cout=1;
l1->val=Sum%10;
}
else
{
*cout=0;
l1->val=Sum;
}
return;
}六、原地修改
当复制的链表具有其他信息，不便于直接复制时，可以先原地复制，再间隔地挑出来。
例题：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return NULL;
Node* cur = head, *prev, *newhead;
while(cur)
{
Node* newNode = new Node(cur->val);
newNode->random = cur->random;
newNode->next = cur->next;
cur->next = newNode;
cur = cur->next->next;
}
prev = head;
newhead = head->next;
while(prev)
{
cur = prev->next;
if(cur->random)
cur->random = cur->random->next;
prev = prev->next->next;
}
prev = head;
while(prev)
{
cur = prev->next;
prev->next = prev->next->next;
prev = prev->next;
cur->next = prev ? prev->next : NULL;
}
return newhead;
}
};- class Solution {
- public:
- Node* copyRandomList(Node* head) {
- if(!head) return NULL;
- Node* cur = head, *prev, *newhead;
- while(cur)
- {
- Node* newNode = new Node(cur->val);
- newNode->random = cur->random;
- newNode->next = cur->next;
- cur->next = newNode;
- cur = cur->next->next;
- }
- prev = head;
- newhead = head->next;
- while(prev)
- {
- cur = prev->next;
- if(cur->random)
- cur->random = cur->random->next;
- prev = prev->next->next;
- }
- prev = head;
- while(prev)
- {
- cur = prev->next;
- prev->next = prev->next->next;
- prev = prev->next;
- cur->next = prev ? prev->next : NULL;
- }
- return newhead;
- }
- };
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head) return NULL;
Node* cur = head, *prev, *newhead;
while(cur)
{
Node* newNode = new Node(cur->val);
newNode->random = cur->random;
newNode->next = cur->next;
cur->next = newNode;
cur = cur->next->next;
}
prev = head;
newhead = head->next;
while(prev)
{
cur = prev->next;
if(cur->random)
cur->random = cur->random->next;
prev = prev->next->next;
}
prev = head;
while(prev)
{
cur = prev->next;
prev->next = prev->next->next;
prev = prev->next;
cur->next = prev ? prev->next : NULL;
}
return newhead;
}
};七、结合其他算法
例如结合BFS、DFS等搜索办法，DP、DC等优化算法等等
