11
链表操作的一处技巧
source link: https://www.zenlife.tk/fake-list-head.md
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
链表操作的一处技巧
2016-02-18
以前学数据结构，老师给我们讲带头结点的单链表和不带头结点的单链表。
对普通链表(不带头结点单链表)的操作，比如做删除或者插入，需要考虑一些特殊场景：1.判断是否空链表；2.操作头结点跟其它不一样，因为可能会修改head指针
struct ListNode* list_delete1(struct ListNode *l, int n) {
if (l == NULL) return NULL;
if (l->val == n) {
return l->next;
}
struct ListNode *prev = l;
struct ListNode *cur = l->next;
while(cur) {
if (cur->val == n) {
prev->next = cur->next;
return l;
}
prev = cur;
cur = cur->next;
}
return l;
}带头结点的链表浪费一个结点的空间，换来的是代码的简化，因为不需要对头结点特殊考虑，所有操作都是一致的。
自己想到的一个小技巧，有些场合可以伪造一个fake的头结点出来，简化代码。
struct ListNode* list_delete2(struct ListNode *l, int n) {
struct ListNode fake;
fake.next = l;
for (struct ListNode *prev=&fake; prev->next; prev=prev->next) {
if (prev->next->val == n) {
prev->next = prev->next->next;
break;
}
}
return fake.next;
}下面的代码是不是比上面精简了？这个技巧在平时写代码或者是刷题什么的都可以用到。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK