单链表算法实战：解锁数据结构核心谜题——移除链表元素

题目如下：

解题过程如下：

给了链表的头结点head就相当于知道了整个链表。

思路1：查找值为val的结点并返回结点位置，删除pos位置的结点。
涉及循环的嵌套，时间复杂度为O(n^2)：

思考时间复杂度可不可以降为O(n)呢?

思路2：创建新链表，将原链表中值不为val的结点拿下来尾插。
在原链表中修改，涉及到遍历、删除，时间复杂度不太好，那就创建一个新链表，这里并没有申请一个新链表、新结点，而是创建了一个空链表，该链表里有两个指针newHead、newTail，这两个指针还是指向原链表中的结点，通过修改两个新指针的指向来变成一个新的链表。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//创建空链表ListNode* newHead, *newTail;newHead = newTail = NULL;//查找值不为val的结点并拿下来尾插ListNode* pcur = head;while (pcur){if (pcur->val != val){//链表为空if (newHead == NULL){newHead = newTail = pcur;}//链表不为空else{newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}return newHead;
}

点击运行发现Case1“解答错误”：

OJ代码有bug怎么办？VS调试技能用起来：

//test.c
struct ListNode{int val;struct ListNode *next;};typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//创建空链表ListNode* newHead, * newTail;newHead = newTail = NULL;//查找值不为val的结点并拿下来尾插ListNode* pcur = head;while (pcur){if (pcur->val != val){//链表为空if (newHead == NULL){newHead = newTail = pcur;}//链表不为空else{newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}return newHead;
}
int main()
{//手动构造一个链表SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node5 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node6 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node7 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;node2->data = 2;node3->data = 6;node4->data = 3;node5->data = 4;node6->data = 5;node7->data = 6;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node6;node6->next = node7;node7->next = NULL;SLTNode* plist = node1;int val = 6;ListNode* newHead = removeElements(plist, val);return 0;
}

最后发现问题所在：存储数据5的尾结点的指针域指向存储6的结点，应该把链表的尾结点的next指针置为空。

我们发现修改后点击运行还是会出现错误，是因为当这个链表是空链表时，不进入循环，newTail是空指针，newTail->next就是对空指针的解引用操作，这不符合语法规则，所以会报错：

完整代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {//创建空链表ListNode* newHead, *newTail;newHead = newTail = NULL;//查找值不为val的结点并拿下来尾插ListNode* pcur = head;while (pcur){if (pcur->val != val){//链表为空if (newHead == NULL){newHead = newTail = pcur;}//链表不为空else{newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}if (newTail)newTail->next = NULL;return newHead;
}