单链表算法实战：解锁数据结构核心谜题——移除链表元素
标题如下：https://i-blog.csdnimg.cn/direct/a860c63bcaf14a8985539cd3e4223fd2.png
解题过程如下：
给了链表的头结点head就相称于知道了整个链表。
思绪1：查找值为val的结点并返回结点位置，删除pos位置的结点。
涉及循环的嵌套，时间复杂度为O(n^2)：
https://i-blog.csdnimg.cn/direct/9bc2a3e7beea4bf9b0265e4cffd5f12b.png
思考时间复杂度可不可以降为O(n)呢?
思绪2：创建新链表，将原链表中值不为val的结点拿下来尾插。
在原链表中修改，涉及到遍历、删除，时间复杂度不太好，那就创建一个新链表，这里并没有申请一个新链表、新结点，而是创建了一个空链表，该链表里有两个指针newHead、newTail，这两个指针还是指向原链表中的结点，通过修改两个新指针的指向来变成一个新的链表。
https://i-blog.csdnimg.cn/direct/d5b9530fb1eb459ebb4ffd8aa4a194a5.png
/**
* 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“解答错误”：
https://i-blog.csdnimg.cn/direct/ea43431297134fd3a08c51d9382afb75.png
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;
}
https://i-blog.csdnimg.cn/direct/bd42bd3b031741baa0e419922c108dc9.png
最后发现问题所在：存储数据5的尾结点的指针域指向存储6的结点，应该把链表的尾结点的next指针置为空。
https://i-blog.csdnimg.cn/direct/f8009cf3f66a46d1a426685315045f34.png
我们发现修改后点击运行还是会出现错误，是因为当这个链表是空链表时，不进入循环，newTail是空指针，newTail->next就是对空指针的解引用操纵，这不符合语法规则，所以会报错：
https://i-blog.csdnimg.cn/direct/2d4ed91e122e4586a81161de84913834.png
完整代码如下：
/**
* 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;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]