概述
- 上述四个题目，算法的技巧都在建立虚拟头结点，来统一操作
分析
-
对于链表来说，头结点相当于其他结点处在一个特殊位置：其他结点都有前、后结点（尾结点的后结点时NULL)，而头结点确没有前结点
-
所以，经常会需要额外考虑头结点的处理
-
为了同一操作，可以为原始链表添加一个虚拟头结点，指向原始头结点，使得对于原始链表来说，所有结点都是一样的结构，用于前、后结点
思路
如何添加虚拟头结点？
-
ListNode *virtual_head = new ListNode(); virtual_head -> next = head;
代码
203
移除链表中满足Node.val == val 的节点，通过使用虚拟头结点来统一对原始链表头结点的删除操作
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 构造虚拟头结点，链接原始链表
ListNode *virtual_head = new ListNode();
virtual_head->next = head;
// 省略了delete删除物理结点的操作
ListNode *pre_ptr = virtual_head;
ListNode *work_prt = head;
while(work_prt) {
if (work_prt -> val == val) {
pre_ptr -> next = work_prt->next; // 逻辑上,在链表中删除该结点
work_prt = pre_ptr->next; // 下一个工作结点
} else {
pre_ptr = pre_ptr -> next;
work_prt = work_prt -> next;
}
}
return virtual_head -> next;
}
};
707
利用虚拟头结点来统一操作
class MyLinkedList {
public:
struct LinkNode{ // 内部结点实现
int val;
LinkNode *next;
};
MyLinkedList() {
size = 0;
virtual_node = new LinkNode(); // 创建虚拟头结点
}
int get(int index) {
if (index < 0 || index >= size) return -1;
LinkNode *work_ptr = virtual_node; // 非特殊必要，wokr_ptr从虚拟头结点开始较好
int count = 0;
while(work_ptr -> next) { // 循环判断
work_ptr = work_ptr -> next;
if (count == index) return work_ptr -> val;
++count;
}
return -1;
}
void addAtHead(int val) {
LinkNode *new_node = new LinkNode();
new_node -> val = val;
new_node -> next = virtual_node -> next;
virtual_node -> next = new_node;
++size;
}
void addAtTail(int val) {
LinkNode *new_node = new LinkNode();
new_node -> val = val;
LinkNode *work_ptr = virtual_node;
while(work_ptr -> next) work_ptr = work_ptr -> next;
work_ptr -> next = new_node;
++size;
}
void addAtIndex(int index, int val) {
if (index <= 0) {
addAtHead(val);
return;
}
if (index == size){
addAtTail(val);
return;
}
if (index > size) return;
LinkNode *new_node = new LinkNode();
new_node -> val = val;
LinkNode *pre_ptr = virtual_node;
LinkNode *work_ptr = virtual_node -> next; // 特殊情况，work_ptr从实际的头结点,即virtual_head -> next开始
int count = 0;
while(work_ptr){ // while条件
if(count == index) {
pre_ptr -> next = new_node;
new_node -> next = work_ptr;
break;
}
work_ptr = work_ptr -> next;
pre_ptr = pre_ptr -> next;
++count;
}
++size;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
LinkNode *pre_ptr = virtual_node;
LinkNode *work_ptr = virtual_node -> next; // 特殊情况
int count = 0;
while(work_ptr){
if(count == index) {
pre_ptr -> next = work_ptr -> next;
delete work_ptr;
break;
}
pre_ptr = pre_ptr -> next;
work_ptr = work_ptr -> next;
++count;
}
--size;
}
private:
int size; // 记录链表长度；
LinkNode *virtual_node; // 虚拟头结点
};
206
创建虚拟头结点，利用头插法构建原始链表的逆序链表
class Solution {
public:
// 头插法
ListNode* reverseList(ListNode* head) {
ListNode * virtual_head = new ListNode();
ListNode *work_ptr = head;
while(work_ptr) {
ListNode *temp = work_ptr -> next;
work_ptr -> next = virtual_head -> next;
virtual_head -> next = work_ptr;
work_ptr = temp;
}
return virtual_head->next;
}
};
24
利用虚拟头结点，统一对原始链表头结点的操作
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *virtual_head = new ListNode();
virtual_head -> next = head;
ListNode *pre_ptr = virtual_head;
ListNode *work_ptr = head;
while(work_ptr && work_ptr -> next) {
// 更新过程要想清楚
ListNode *next_ptr = work_ptr -> next;
pre_ptr -> next = next_ptr;
work_ptr -> next = next_ptr -> next;
next_ptr -> next = work_ptr;
pre_ptr = work_ptr;
work_ptr = pre_ptr -> next;
}
return virtual_head -> next;
}
};
考虑：
当我们使用了虚拟头结点时，工作指针wokr_ptr从虚拟头结点开始较好，此时利用while遍历循环的条件是while(work_ptr -> next)
因为只有这样，才能确保第一次的work_ptr一定有效。
如果需要前后两个指针，则work_ptr需要指向work_ptr -> next，此时while遍历循环的条件是while(work_ptr)，因为原始链表可能为空
这段分析，可参考题目707的注释理解
