链表（下）

如何轻松写出正确的链表代码

链表技巧

技巧一：理解指针或引用的含义

1. 指针中存储了这个变量的内存地址
2. p结点中的next指针存储了q节点的内存地址

p->next = q 

技巧二：警惕指针丢失和内存泄漏

p->next = x; //将p的next指针指向x结点
x->next = p->next; //将x的结点的next指针指向b结点

1. 第一行：p->next结点指向x
2. 第二行: x->next结点指向p->next, 而p->next已经指向x，所以p->next = x, 导致链接断开
3. 之后的所有结点失去指针，导致内存泄漏

技巧三：利用哨兵简化实现难度

1. 普通的链表插入

   void insert(Node *head, Node *newNode) 
   {
   	if (head == null) {
   		head = newNode;
   	}  else {
   		nextNode->next = head;
   		head = nextNode;
   	}
   }

2. 哨兵模式 （本章重点）

   void insert(Node *head, Node *newNode) 
   {
   	newNode->next = head->next->next;
   	head->next = newNode;
   }

   

技巧四：重点留意边界条件处理

链表在以下4种情况下是否正常工作

1. 如果链表为空时
2. 如果链表只包含一个结点时
3. 如果链表只包含两个结点时
4. 代码逻辑在处理头结点和尾结点时

技巧五：举例画图，辅助思考

技巧六：多写多练，没有捷径

1. 单链表反转
2. 链表中环的检测
3. 两个有序的链表合并
4. 删除链表倒数第n个结点
5. 求链表的中间结点