算法与数据结构基础 - 链表(Linked List)增删改查
链表基础
链表(Linked List)相比数组(Array)，物理存储上非连续、不支持O(1)时间按索引存取；但链表也有其优点，灵活的内存管理、允许在链表任意位置上插入和删除节点。单向链表结构一般如下：
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
链表增删改查
要完成链表节点的查找、插入、删除与修改，需要特别留意前后指针的修改、空指针的处理。总得来说链表增删改查分三步：1/定义结束条件(一般为到达链表尾) 2/遍历链表 3/遍历过程中完成增删改查。
一些情况下会用哑节点(dummy node)来更方便对链表增删改查，这有时可以减少代码量。比如 LeetCode题目 203. Remove Linked List Elements：
// 203. Remove Linked List Elements
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummy=new ListNode(0);
dummy->next=head;
ListNode* cur=dummy;
while(cur->next!=NULL){
if(cur->next->val==val) cur->next=cur->next->next;
else cur=cur->next;
}
return dummy->next;
}
以上如果不使用dummy node，如果head是要被删除的节点，则需要特殊判断和处理，使用dummy node则化解了这个问题。
THE END
