单链表应用：经典算法题与通讯录实现

第一部分：单链表经典算法 OJ 题

1.1 移除链表元素

解题思路：

1. 在原链表上进行修改，创建 pcur 和 prev 两个变量，遍历原链表，最后返回，但是需要注意头节点也要被释放的情况。
2. 创建一个带哨兵位的新链表，将符合条件的节点接到新链表后面，然后返回哨兵位的 next 节点，注意尾节点的 next 需要置为 NULL。

易错点： 如果原链表是空链表，那么直接返回空链表。

代码展示：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    if(head==NULL) {
        return NULL;
    }
    ListNode* newhead,* newtail;
    newhead=newtail=(ListNode*)malloc(sizeof(ListNode));
    ListNode* pcur=head;
    while(pcur) {
        if(pcur->val!=val) {
            newtail->next=pcur;
            newtail=newtail->next;
        }
        pcur=pcur->next;
    }
    newtail->next=NULL;
    ListNode* ret=newhead->next;
    free(newhead);
    return ret;
}

1.2 反转链表

题目描述：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

解题思路：

• 使用三个指针：prev（前一个节点）、curr（当前节点）、next（下一个节点）
• 遍历过程中，将当前节点的 next 指向前一个节点，然后整体后移

代码实现：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    ListNode* n1,*n2,*n3;
    (head==)  head;
    n1=,n2=head,n3=head->next;
    (n2) {
        n2->next=n1;
        n1=n2;
        n2=n3;
        (n3) n3=n3->next;
    }
     n1;
}