书中用struct实现了节点(node):

struct ListNode{
    int m_nValue;
    ListNode* m_pNext;
};

然后用ListNode **head表示链表的头。

个人不喜欢这样表示。我相信现在应该没有多少人愿意去看有“指针的指针”的程序。一个程序中出现指针是很正常的，但是出现“指针的指针”就很讨厌了。属于overuse of pointers。不仅容易出错而且降低程序可读性。还有一点就是这样表示链表明显能看出有C-style。没有充分发挥C++语言良好的封装性。我没用书上的例程。参考了[1]用class实现了list。（注意到[1]中的代码有bug：如果用原程序中的Delete函数从头开始删除节点，那么就会产生segmentation fault)。

class Node{
    int data; 
    Node* next;
public:
    Node(){};
    void SetData(int aData) {data = aData;}
    void SetNext(Node* aNext){ next = aNext;}
    int GetData(){ return data;}
    Node* GetNext() {return next;}
};


class List{
    Node *head;
public:
    List() {head = NULL;}
    void Print();
    void Append(int _data);
    void Delete(int _data);
    void PrintReversely();
};

我参考了[2]重新写了List::Delete(int) 函数如下：

void List::Delete(int _data){ 
    // empty list
    if(head == NULL)
	return;
   
    Node* ToBeDeleted = NULL;
    if(head->GetData() == _data){
	ToBeDeleted = head;
    	head = head->GetNext();
    }else{
	// create a copy of list head pointer
	Node* ptr = head;
	while(ptr->GetNext() != NULL){
	    if(ptr->GetNext()->GetData() == _data ){
		// ptr --> [ptr.next] --> ...
		Node* tmp = ptr->GetNext()->GetNext();
		ToBeDeleted = ptr->GetNext();
		ptr->SetNext(tmp);
		break;
	    }else{
		ptr = ptr->GetNext();
	    }
	}	 
    }
    if(ToBeDeleted != NULL){
	delete ToBeDeleted; // free the memory it pointed to
	ToBeDeleted = NULL; //point the dangling ptr to null
    }
}

在删除一个指针时，为避免内存泄露，要首先进行delete操作释放内存,此时该指针变为dangling pointer。然后应将此迷途指针重置为NULL.[3][4]

最后逆序打印链表的函数是照着书里的思路来的。用STL中的stack实现：

void List::PrintReversely(){
    stack<Node*> nodes;
    Node* ptr = head;
    if(ptr==NULL){
	cout<<" Empty List"<<endl;
	return;
    }

    while(ptr!=NULL){
	nodes.push(ptr);
	ptr= ptr->GetNext();
    }
    cout<<"NULL ";
    while(!nodes.empty()){
	Node* tmp = nodes.top();
	cout<<" <-- ";
	cout<<tmp->GetData();
	nodes.pop();
    }
    cout<<endl;
}

完整程序在：

git clone https://github.com/zhutiti/Hehaitao.git

参考：

[1] C++ singly linked list: http://login2win.blogspot.com/2008/07/c-singly-linked-lists.html

[2] How do I delete a node from linked list http://stackoverflow.com/questions/3732399/how-do-i-delete-a-node-from-linked-list-c

[3] C++ deleting a pointer http://stackoverflow.com/questions/13223399/c-deleting-a-pointer

[4] Dangling pointer - Wiki http://en.wikipedia.org/wiki/Dangling_pointer