1. 实现方式：
- 经典实现方式——结构体
struct Node {
Node (int data):data(data),next(NULL){}
int data;
Node *next;
};
int main(){
Node *head = NULL;
head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
Node *p = head;
while (p != NULL) {
printf("%d->", p->data);
p=p->next;
}
}
- 特殊实现方式——数组
int data[10]; // 数据域
int next[10]; // 指针域
void add(int ind, int p, int val){
// 在ind节点后插入一个值为val的p节点
next[p] = next[head];
next[ind] = p; // 完成指针域的交接
data[p] = val;
return ;
}
int main(){
int head = 3;
data[head] = 0;
add(head, 5, 1);
add(5, 2, 2);
add(2, 7, 3);
add(7, 9, 100);
int p = head;
while (p != 0) {
printf("%d->", data[p]);
p = next[p];
}
printf("\n");
return 0;
}
从以上两种实现方式其实可以看出，链表的本质就是数据域和指针域的配合使之在物理关系上形成一个连续的存储关系。
类似应用场景譬如操作系统的动态内存分配、LRU缓存淘汰算法。
2. 环形链表问题：
2.1 怎么判断链表中是否有环？
思路一：哈希表，依次遍历每个节点，并存入哈希表中。当要存入的节点已经存在于哈希表中，说明链表有环，遍历结束。
思路二：快慢指针
快指针每次走两步，慢指针每次走1步。
- 如果没环，慢指针永远追不上快指针。
- 如果有环，快慢指针一定会在环中相遇。
bool hasCycle(Node *head) {
if (head==nullptr || head->next == nullptr) return false; // 如果链表为空，或者只有一个节点，显然不能成环。
Node *p = head, *q = head;
do {
p = p->next; // 慢指针
q = q->next->next; // 快指针
} while (p!=q && q);
return q != nullptr; // q不为空，则p==q，说明有环
}
leetcode-202 快乐数
一个数字通过若干次的变换规则（各个位数的平方和），如果能变换到1的话，这个数就是快乐数。
思路：把变换的过程视作链表的遍历。进而判断链表是否有环，
如果遍历到某个节点为1，说明没环，就是快乐数
如果遍历到重复的节点，说明有环，就不是快乐数。
int getNext(int x) {
int z = 0;
while (x) {
z += (x%10) * (x%10);
x /= 10;
}
return z;
}
bool isHappy(int n) {
int p = n, q = n;
do {
p = getNext(p);
q = getNext(getNext(q));
} while (p != q && q != 1);
return q==1;
}
2.2 寻找环的起点位置
快慢指针的做法：
- 快慢指针从起点一同出发
- 快慢指针相遇。
- 接着，一个从起点出发，一个从相遇点出发，保持相同的速度依次往前走。再次相遇的地方就是成环的起点。
证明：
假设当慢指针走到环入口的时候：
- 慢指针走过
a的距离，快指针走过2a的距离 - 快指针到环的入口还剩下
x的距离。即环的长度为l=a+x那么长。 - 此时两指针前进的方向都是沿环且同向。依据追及问题：那么快指针想要追上慢指针需要走过
2x的距离。而此时的相遇点走到环的入口刚好有l-x=a的距离。这与起点走到环入口的距离a是一样的。
// 这里假定成环
Node *detectCycle(Node *head) {
Node *p = head, *q = head;
do {
p = p->next;
q = q->next->next;
} while (p!=q); // 找到第一个环内相遇点。
p = head;
while (p!=q) {
p = p->next;
q = q->next;
} // 当找到环起点的时候退出循环
return q;
}
3. 链表反转问题：
3.1 普通做法：
定义三个指针：pre、cur、next。依次处理好每一轮的指针域的交接问题。
Node *reverseList(Node *head) {
if(head == nullptr || head->next == nullptr) return head; // 链表为空或者只有一个节点，没必要反转。
Node *pre = nullptr, *cur = head, *p = cur->next;
while (cur) {
cur->next = pre; // cur到next之间断开，next指向pre的位置，
pre = cur; // pre往前移动到cur的位置
(cur = p) && (p = p->next); // cur往前移动到p的位置；如果p的位置不为空，p也移动到下一个位置。
}
return pre; // 返回新的头节点
}
3.2基于递归的做法
Node *reverseList(Node *head) {
if(head == nullptr || head->next == nullptr) return head;
Node *tail = head->next , *p = reverseList(head->next); // 获取到反转后链表的头节点p；tail存储反转后的链表尾节点
head->next = tail->next;
tail->next = head; // 这两步相当于是在将head插入到反转后的链表的尾节点。
return p;
}
3.3 反转前n个节点
Node *reverseN(Node *head, int n) {
if(n==1)return head;
Node *tail=head->next, *p = reverseN(head->next, n-1);
head->next = tail->next;
tail->next = head;
return p;
}
3.3 反转第m-n的节点
Node *reverseN(Node *head, int n) {
if(n==1) return head;
Node *tail = head->next, *p = reverseN(head->next, n-1);
head->next = tail->next;
tail->next = head;
return p;
}
Node *reverseBetween(Node *head, int m, int n) {
Node ret(0, head), *p = &ret; // 定义虚拟节点ret
int cnt=n-m+1; // 记录反转part的节点个数
while (--m) p = p->next; // 走到反转part的前一个节点。
p->next = reverseN(p->next, cnt); // 调用封装好的代码
return ret.next;// 返回反转后的链表头节点。
}
注意：虚拟头节点一般用在头节点有可能发生改变的情况。
3.3 k个一组反转链表
Node *__reverseN(Node *head, int n) { // 熟悉的反转逻辑
if(n==1) return head;
Node *tail = head->next, *p = __reverseN(head->next, n-1);
head->next = tail->next;
tail->next = head;
return p;
}
Node *reverseN(Node *head, int n) {
int cnt=n;
// 首先判断是否满n个节点，如果不满就没有必要反转
Node *p = head;
while (--n && p) p = p->next;
if (p == nullptr) return head;
// 再封装一层
return __reverseN(head, cnt);
}
Node *reverseGroup(Node *head, int k) {
Node ret(0,head), *p = &ret, *q = head; // p 记录每次反转部分的前一个节点，q记录每次反转部分的头节点，所以需要设一个虚拟头ret
while ((p->next = reverseN(q, k)) != q) { // 只要不相等，就说明反转成功
p = q;
q = q->next;
}
// 如果没有反转，就说明结束了
return ret.next; // 不能返回head,因为此时head已经指向链表结尾。
}
4. 旋转链表
4.1循环左移k位
策略：
- 找到链表的尾节点，进行首尾相连
- 从尾节点出发，继续走k步，断开当前节点和下一个节点的连接。
- 返回下一个节点。
// 循环右移时，逻辑也是差不多的。
Node *rotateRight(Node *head, int k) {
if(head==nullptr || head->next == nullptr) return head;
Node *p = head;
int n = 1; // 节点计数
while (p->next) p = p->next, n++;
p->next = head; // 首尾相连
k %= n; // 防止重复转圈。
k = n-k; // 循环右移跟左移的逻辑在这里相反，左移是k
while (k--) p = p->next;
head = p->next; // 更新头节点
p->next = nullptr; // 断开首位链接
return head; // 返回新的头节点
}
5. 删除链表节点
5.1删除链表的倒数第n个节点
-
链表：(ret)->1->2->3->4->5->null
假设要删除倒数第2个节点(4号)，则我需要站在3号节点的位置： - 先让一个q节点从head节点向前走2步，到达3号节点。
- 然后在和p节点（从虚拟头节点ret开始）一起向前走，直到q节点走到null后（又走了3步），p节点所在的位置即是3号节点。
Node *removeNthFromEnd(Node *head, int n) {
Node ret(0, head), *p = &ret, *q = head;
while (n--) q = q->next; // q先走n步
while (q) q=q->next, p=p->next; // 一直走到q为null为止，p所在的位置的下一位就是倒数第n位
p->next = p->next->next;
return ret.next;
}
5.2删除排序链表中的重复节点1（保留一个）
策略：判断p节点跟p->next是否相等，如果相等，持续性地删除p->next 如果不等，p=p->next
Node *deleteDuplicates(Node *head){
if(head == nullptr || head->next == nullptr) return head;
Node *p = head;
while (p->next) {
if(p->val == p->next->val){
p->next = p->next->next;
} else {
p = p->next;
}
}
return head;
}
5.3 删除排序链表中的重复节点2（全部删除）
Node *deleteDuplicates(Node *head){
if(head == nullptr || head->next == nullptr) return head;
Node ret(0, head), *p = &ret, *q; // 因为有可能删除头节点，所以需要一个虚拟头
while (p->next) {
if(p->next->val == p->next->next->val){
q = p->next->next;
while (q->val == p->next->val) p = p->next;
p->next = q; // 直接跳过中间重复的节点，连到新的节点
} else {
p = p->next;
}
}
return ret.next;
}
