在单链表中删除指定值的节点

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“在单链表中删除指定值的节点”这一题目的C++复现。

　　本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

　　感谢左程云老师的支持。

【题目】：

　　给定一个链表的头节点 head 和一个整数 num，请实现函数将值为 num 的节点全部删除。

　　例如，链表为 1->2->3->4->NULL，num=3，链表调整后为：1->2->4->NULL。

【思路】：

　　解法：注意头节点的处理。

【编译环境】：

　　CentOS6.7（x86_64）

　　gcc 4.4.7

【实现】：

　　实现及测试代码：

 1 /*
 2  *文件名：list_remove.cpp
 3  *作者：
 4  *摘要：在单链表中删除指定值的节点
 5  */
 6 
 7 #include <iostream>
 8 
 9 using namespace std;
10 
11 class Node
12 {
13 public:
14     Node(int data)
15     {
16         value = data;
17         next = NULL;
18     }
19 public:
20     int value;
21     Node *next;
22 };
23 
24 Node* removeNode(Node *head,int num)
25 {
26     Node *cur = NULL;
27     while(NULL != head)
28     {
29         if(num != head->value)
30             break;
31         cur = head;
32         head = head->next;
33         delete cur;
34     }
35     
36     cur = head;
37     Node *pre = head;
38     while(NULL != cur)
39     {
40         if(num == cur->value)
41         {
42             pre->next = cur->next;
43             delete cur;
44         }
45         else
46         {
47             pre = cur;
48         }
49         cur = pre->next;
50     }
51     return head;
52 }
53 
54 void printList(Node *head)
55 {
56     while(NULL != head)
57     {
58         cout << head->value << " ";
59         head = head->next;
60     }
61     cout << endl;
62 }
63 
64 int main()
65 {
66     Node *head = NULL;
67     Node *ptr = NULL;
68     
69     for(int i =1;i<7;i++)//构造链表
70     {
71         if(NULL == head)
72         {    
73             head = new Node(i);
74             ptr = head;
75             continue;
76         }
77         ptr->next = new Node(i);
78         ptr = ptr->next;
79         ptr->next = new Node(i);
80         ptr = ptr->next;    
81     }
82     cout << "before remove:" << endl;
83     printList(head);
84     cout << "after remove:" << endl;
85     head = removeNode(head,2);    
86     printList(head);
87     return 0;
88 }

View Code

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。