leetcode--链表总结
1. 两个链表相加
(1) 模拟两个数相加（445. Add Two Numbers II,Medium）
思路：两个链表是两个加数的逆序，所以两个链表对应位置相加，再翻转结果，就是两个加数的和。其中要主要进位，进位最大是1，且计算到最后要判断是否有进位，有的话要创建节点。
(2) 两个链表元素相加（2. Add Two Numbers, Medium ）
思路：比445简单，直接对应位置元素相加即可，不用翻转链表。但也要注意进位。
2. 链表翻转(逆序)
(1) 指定某一段子链翻转
（92. Reverse Linked List II, Medium）
思路：指定第m到第n个节点翻转，先用一个节点指向第m个节点的前驱，后面n-m+1个节点都向这个位置插入。
(2) 每个等长的子链翻转
（24. Swap nodes in pairs, Medium）
思路：24.对每两个元素进行翻转。需要两个指针指向这个pair，通过将前面的节点放在后面的节点后面来翻转两个节点比把后面的节点放在前面的节点前面操作简单，因为往前插入，需要有前一个的指针。
（25.Reverse Nodes in k-Group, Hard）
思路：25.对每k个元素进行翻转，最后剩余不够k个元素则不进行翻转。先要计算链表中元素个数，这个个数也作为剩余的元素数量，根据这个数量判断是否继续下一组k个元素翻转，每次翻转一组元素后要更新这个值。每次k个元素采用头插法，只需要固定二个位置，一个是头节点（需要插入元素的前驱结点），一个是需要移动的节点的前驱结点。时间复杂度O(2n)，空间复杂度O(1)
class Solution {
public:
int Size(ListNode *head)
{
int s = 0;
ListNode *p = head;
while(p)
{
++s;
p = p->next;
}
return s;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if(!head || k == 1 || Size(head) < k) // 注意：k=1的时候不用翻转元素
return head;
ListNode newhead(0); // 注意：head是会被翻转的，为了头节点和其他节点同样处理，所以这里引入临时头节点。
newhead.next = head;
ListNode *pre = &newhead;
ListNode *p = pre->next;
int i = Size(head);
while(i >= k)
{
ListNode *rear = p;
for(int i = 0; i < k; ++i)
{ // 下面利用头插法逆置链表
ListNode *next = p->next;
p->next = pre->next;
pre->next = p;
p = next;
}
rear->next = p;
pre = rear;
i -= k; // 每次减去k个
}
return newhead.next;
}
};
(3) 判断链表是否是回文（234. PalindromeLinked List, Easy）
思路：先找到中间的节点，翻转后半个链表，之后和前半部分链表比较，
时间复杂度O(n)，空间复杂度O(1)
(4) 逆序（整个链表翻转）(206. Reverse LinkedList, Easy）
a. 头插法
思路：每次都向头节点的后面插入元素，需要定义头节点)
b. 就地逆置
思路：每次将节点放在链表的开头，移动头节点的指针
3. 旋转链表
（61. Rotate List, Medium）
向左旋转k个元素=向右旋转n-k个元素
思路：后半部分（k, n-1）和前半部分（0，k-1）颠倒位置。首先k可能大于n，所以k%=n，之后将链表首尾相连，形成环，从链表开头移动n-k个位置断开环，k个位置的下一个位置作为head，即为所求。
4. 链表去重
(1) 对于连续重复的元素保留第一个或最后一个 (83. RemoveDuplicates from Sorted List, Easy)
(2) 重复全部删除（82. RemoveDuplicates from Sorted List II, Medium）
思路：每个节点与后继进行比较，相同就把前面的删除，利用flag标记删除，后继节点如果与他们后继不同，但flag为true，说明他与前面删除的节点是相同的，所以也要删除。
5. 链表合并
两个升序排序的链表合并（21. Merge Two Sorted Lists, Easy）
6. 链表划分
(1) 小于x的节点在前面，大于x的节点在后面（86. Partition List, Medium）
(2) 奇数放在前面，偶数放在后面（328. Odd EvenLinked List, Medium）
思路：定义两个头节点，分别作为奇数链表的头节点，和偶数链表的头节点。遍历一次链表划分奇偶，之后将两个链表链接起来。
7. 移除指定节点
(1) 移除倒数第k个节点（19. Remove Nth Node From End of List, Medium）
思路：利用两个指针，一个指针先向前走k步，之后两个指针每次走一步，直到先走的指针走到链表结尾节点，第二个指针指向的位置就是要删除的节点的前驱，再删除其后的节点。
(2) 移除指定val的元素（237.Delete Node in a Linked List，Easy）（203. Remove Linked List Elements, Easy）
8. 运用快慢指针
(1) 判断链表是否有环（141. Linked List Cycle,Easy）
(2) 寻找带有环的单链表的起始节点（142. Linked ListCycle II, Medium）
思路：先找到快慢指针在链表上的交点，之后从链表的头节点和交点开始移动指针，齐头并进，最后的交点即为所求。
for pointer 1: vt = X+nY+K
for pointer 2: 2vt = X+mY+K (m,n isunknown)
2X + 2nY + 2K = X + mY + K
X+K = (m-2n)Y
(3) 寻找单链表的中心, 判断链表的奇数个元素还是偶数个元素（143. Reorder List, Medium）
Given asingly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
一个指针p1每次走一步，另一个指针p2每次走两步，如果p2最后满足p2&&p2->next = NULL那么链表就是奇数个元素。
思路：143.需要综合运用对链表的多个操作方法。首先利用快慢指针，找到链表的中心并判断链表奇偶，如果是奇数个，则p1向后移动一个位置，这样就将链表分成了两部分。之后将后半部分进行逆序。最后将后半部分的元素分别插入到前半部分元素中间。
寻找单链表的中心, 判断链表的奇数个元素还是偶数个元素：
while(pFast->next)
{
pre = pSlow;
pSlow = pSlow->next;
pFast = pFast->next;
if(!pFast->next)
break;
pFast = pFast->next;
}
If(!pFast)
// 偶数个元素
Else if(!pFast->next)
// 奇数个元素
9. 查找两个链表的公共节点
（160. Intersection of Two Linked Lists, Easy）
思路：先计算两个链表的长度，长的链表将指针移动到和短的链表看齐的位置，之后齐头并进扫描，如果两个指针相同，那么就找到公共节点了。
10. 与其他数据结构和算法结合
(1) 与平衡二叉树结合
使用递增排列的链表创建平衡二叉树BST（109. Convert Sorted List to Binary Search Tree, Medium）
思路：递增排序相当于是平衡二叉树的中序遍历，所以在安放树中每个节点的值时要按照中序遍历树的顺序遍历二叉树，且顺序遍历链表。先利用先序遍历二叉树的方式生成二叉树，再利用中序遍历二叉树给每个节点赋值。
(2) 与二叉树结合
（114. Flatten Binary Tree to Linked List，Medium）
将二叉树以先序遍历的顺序就地转换为单向链表，TreeNode的right指针指向下一个元素。
class Solution {
public:
void preOrder(TreeNode *p, TreeNode *&last) // *&修改指针的指向，传递的是指针的地址，但*传递的是指针指向的地址，在函数外面不会修改指针的指向。
{
if(!p)
return ;
if(!p->left && !p->right)
{
last = p;
cout << p->val << endl;
return ;
}
//TreeNode *left = p->left;// 指向左子树节点的指针也可以不备份
TreeNode *right = p->right;
TreeNode *leftlast = NULL;
TreeNode *rightlast = NULL;
//if(left)
if(p->left)
{
//preOrder(left, leftlast);
preOrder(p->left, leftlast);
//p->left = NULL;
//p->right = left;
p->right = p->left;
p->left = NULL;
last = leftlast; // 注意没有右子树的情况
}
if(right)
{
//cout << right->val << endl;
preOrder(right, rightlast);
if(leftlast) // 注意没有左子树的情况
{
leftlast->right = right;
}
last = rightlast;
}
}
void flatten(TreeNode* root) {
TreeNode *last = NULL;
preOrder(root, last);
}
};
(3) 与排序结合
a. 对链表的节点做直接插入排序（147. InsertionSort List, Medium）
b. 对链表排序，要求时间O(nlogn)，空间O(n)（148. Sort List, Medium）
思路：使用归并排序。每次利用快慢指针指向中间值。
c. 对k个链表合并为一个有序的链表（23. Merge k Sorted Lists, Hard）
是对两个升序链表合并的拓展。
11. 深度拷贝复杂链表
（138. Copy List with Random Pointer, Medium）
链表中每个元素带有随机指针，可以指向任意的节点或是null。难点在于随机指针，想要顺序的深度拷贝链表是行不通的，因为后面节点的还没有创建可能前面的节点就要指向它，还有要考虑如何指向对应的位置。
方法1：所以这里选择借助辅助空间，遍历一次链表，获取原始链表的节点与所在链表中的位置的对应关系，用map<ListNode *, int>存放。并且与此同时创建新的链表，并对val赋值，用vector存放新的链表的元素，因为vector是顺序的，并支持随机访问，便于直接定位到随机指针指向的节点。下面第二次遍历原始链表，对random和next pointer赋值。根据map找到每个节点随机指针的index，这个index与新链表的位置对应，所以可以根据index，从vector中直接找到random。
方法2：
第一步：拷贝每个节点，放在每个被拷贝节点的后面，并将它们链接起来。
第二步：对拷贝的节点的随机指针赋值，指向被拷贝节点随机指针指向的下一个节点。
第三步：将拷贝节点从链表中拿出来，形成一个新链表，即为所求。
比方法1好在于不需要辅助的容器。
上一篇： go-爬虫-百度贴吧（并发版）
下一篇： springboot项目发布