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

标题如下：
  

   解题过程如下：
  给了链表的头结点head就相称于知道了整个链表。
思绪1：查找值为val的结点并返回结点位置，删除pos位置的结点。
涉及循环的嵌套，时间复杂度为O(n^2)：

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

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. typedef struct ListNode ListNode;
9. struct ListNode* removeElements(struct ListNode* head, int val) {
10.     //创建空链表
11.     ListNode* newHead, *newTail;
12.     newHead = newTail = NULL;
14.     //查找值不为val的结点并拿下来尾插
15.     ListNode* pcur = head;
16.     while (pcur)
17.     {
18.         if (pcur->val != val)
19.         {
20.             //链表为空
21.             if (newHead == NULL)
22.             {
23.                 newHead = newTail = pcur;
24.             }
25.             //链表不为空
26.             else
27.             {
28.                 newTail->next = pcur;
29.                 newTail = newTail->next;
30.             }
31.         }
32.         pcur = pcur->next;
33.     }
34.     return newHead;
35. }

复制代码

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

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

1. //test.c
2. struct ListNode{
3.      int val;
4.      struct ListNode *next;
5. };
7. typedef struct ListNode ListNode;
8. struct ListNode* removeElements(struct ListNode* head, int val) {
9.         //创建空链表
10.         ListNode* newHead, * newTail;
11.         newHead = newTail = NULL;
13.         //查找值不为val的结点并拿下来尾插
14.         ListNode* pcur = head;
15.         while (pcur)
16.         {
17.                 if (pcur->val != val)
18.                 {
19.                         //链表为空
20.                         if (newHead == NULL)
21.                         {
22.                                 newHead = newTail = pcur;
23.                         }
24.                         //链表不为空
25.                         else
26.                         {
27.                                 newTail->next = pcur;
28.                                 newTail = newTail->next;
29.                         }
30.                 }
31.                 pcur = pcur->next;
32.         }
33.         return newHead;
34. }
35. int main()
36. {
37.         //手动构造一个链表
38.         SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
39.         SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
40.         SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
41.         SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
42.         SLTNode* node5 = (SLTNode*)malloc(sizeof(SLTNode));
43.         SLTNode* node6 = (SLTNode*)malloc(sizeof(SLTNode));
44.         SLTNode* node7 = (SLTNode*)malloc(sizeof(SLTNode));
47.         node1->data = 1;
48.         node2->data = 2;
49.         node3->data = 6;
50.         node4->data = 3;
51.         node5->data = 4;
52.         node6->data = 5;
53.         node7->data = 6;
56.         node1->next = node2;
57.         node2->next = node3;
58.         node3->next = node4;
59.         node4->next = node5;
60.         node5->next = node6;
61.         node6->next = node7;
62.         node7->next = NULL;
64.         SLTNode* plist = node1;
65.         int val = 6;
66.         ListNode* newHead = removeElements(plist, val);
67.         return 0;
68. }

复制代码

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

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

   完整代码如下：

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. typedef struct ListNode ListNode;
9. struct ListNode* removeElements(struct ListNode* head, int val) {
10.     //创建空链表
11.     ListNode* newHead, *newTail;
12.     newHead = newTail = NULL;
14.     //查找值不为val的结点并拿下来尾插
15.     ListNode* pcur = head;
16.     while (pcur)
17.     {
18.         if (pcur->val != val)
19.         {
20.             //链表为空
21.             if (newHead == NULL)
22.             {
23.                 newHead = newTail = pcur;
24.             }
25.             //链表不为空
26.             else
27.             {
28.                 newTail->next = pcur;
29.                 newTail = newTail->next;
30.             }
31.         }
32.         pcur = pcur->next;
33.     }
34.     if (newTail)
35.         newTail->next = NULL;
36.     return newHead;
37. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。