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

题目如下：

解题过程如下：

给了链表的头结点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;
}