链表的基本概念
链表是一种递归的数据结构，它或空、或指向一个结点的引用，该节点还有一个元素和一个指向另一条链表的引用。
涉及到的考点
数组与链表的区别：
- 从内存分配和存储来说：数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败；链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；；数组分配的内存是连续的，而链表在内存中的地址是不连续的；数组的存储密度相较于链表来说更大。
- 从存取方式来说：数组可以顺序存取或者随机存取，而链表只能顺序存取；查找时，数组更快更简洁；插入和删除时，链表更容易。
单链表、双向链表、循环链表：
双向链表相比与单链表的优势在于它同时支持高效的正向及反向遍历，并且可以方便的在链表尾部删除结点（单链表可以方便的在尾部插入结点，但不支持高效的表尾删除操作）
循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。
单链表常见的算法
1. 在 O(1) 时间复杂度内删除链表结点
题目描述：给定链表的头指针和一个节点指针，在o(1) 时间内删除该节点。
分析：我们只需要用下一个节点的数据覆盖要删除的节点，就可以达到题目要求，但是当节点是尾节点等特殊情况，就需要另行讨论了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| void deleteNode(ListNode *head,ListNode* node) {
if (head == NULL && node == NULL) {
return;
}
if (node -> next != NULL ) { // 一般正常情况
ListNode *nextNode = node ->next;
node->val = nextNode->val;
node->next = nextNode->next;
delete nextNode;
nextNode = NULL;
} else if (head == node){ // 链表中只有一个节点
delete node;
node = NULL;
head = NULL;
} else { // 要删除的节点是尾节点
ListNode *p = head;
while (p->next != node) {
p = p->next;
}
p->next = node->next;
delete node;
node = NULL;
}
}
|
2. 单链表的转置
题目描述：输入一个单向链表，输出逆序反转后的链表。
分析：单链表的转置，算是比较基本的链表的算法了。通常的思路是用三个指针循环一遍遍历链表就可以实现；当然，我们也可以通过递归的方法来实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
ListNode* reverse(ListNode *head) {
if (head == NULL || head -> next == NULL) {
return head;
}
ListNode *p = NULL, *q = NULL;
while (head != NULL) {
p = head->next;
head->next = q;
q = head;
head = p;
}
return q;
}
ListNode* reverse_Recursion(ListNode *head) {
if (head == NULL || head -> next == NULL) {
return head;
}
ListNode *newHead = reverse_Recursion(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
|
3. 求链表倒数第 K 个节点
题目描述：输入一个单向链表，输出该链表中倒数第 K 个节点，链表的倒数第0个节点为链表的尾指针。
分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| ListNode* FindKthToTail(ListNode* head, unsigned int k) {
if (head == NULL || k == 0) {
return NULL;
}
ListNode* pAhead = head;
ListNode* pBehind = NULL;
for (int i = 0; i < k-1; ++i) {
if (pAhead -> next != NULL) {
pAhead = pAhead->next;
} else {
return NULL;
}
}
pBehind = head;
while (pAhead->next != NULL) {
pAhead = pAhead -> next;
pBehind = pBehind -> next;
}
return pBehind;
}
|
4. 求链表的中间节点
题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。
5. 合并两个排序的链表
题目描述：将两个已排好序的单链表合并成一个链表
6. 交换相邻的节点
题目描述：给定一个链表，交换每两个相邻的节点并返回它的头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| ListNode* swapPairs(ListNode* head) {
ListNode *newHead = new ListNode(0);
newHead->next = head;
ListNode *preNode = newHead, *curNode = head;
while (curNode != NULL && curNode->next != NULL) {
preNode->next = curNode->next;
curNode->next = preNode->next->next;
preNode->next->next = curNode;
preNode = curNode;
curNode = curNode->next;
}
head = newHead->next;
delete newHead;
return head;
}
|
7. 奇偶链表
题目描述：给定一个单链表，将所有奇数节点组合在一起，然后是偶数节点。
分析： 奇节点的下一个节点恰好就是偶节点的下一个节点（1的下一个节点应该是2的下一个节点，也就是3），而偶节点的下一个节点也恰好是奇节点是下一个节点。这样我们就可以只通过odd和even两个变量来遍历了，既省去了用来遍历的head，也省去了一个变量
1
2
3
4
5
6
7
8
9
10
11
12
| ListNode* oddEvenList(ListNode* head) {
if(head == NULL) return NULL;
ListNode *oddNode = head, *evenNode = head->next, *evenHead = evenNode;
while (evenNode != NULL && evenNode->next != NULL) {
oddNode->next = evenNode->next;
oddNode = oddNode->next;
evenNode->next = oddNode->next;
evenNode = evenNode->next;
}
oddNode->next = evenHead;
return head;
}
|
8. 判断单链表是否存在环
题目描述：输入一个单向链表，判断链表是否有环。
9. 找到环的入口
题目描述：输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？
10. 判断两个链表是否相交
题目描述：给出两个单向链表的头指针（如下图所示）。
比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。
11. 链表有环，如何判断相交
题目描述：上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?
12. 两链表相交的第一个公共节点
题目描述：如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？
链表的应用
1. 大数相加
题目描述： 给出两个非空链表，表示两个非负整数。数字以相反的顺序存储，每个节点都包含一个数字。两非负整数相加，并将其作为链表返回。
分析：
