剑指offer之C++语言实现链表（两种删除节点方式）

1 问题

用C++语言实现链表

2 代码实现

      #include <iostream>
      #include <stdlib.h>
      using namespace std;
      class List
      {
      public:
      	List();
      	~List();
     	List* createNode(int value);//创建节点
     	bool insertNode(List *node);//插入节点
     	void printList();//打印节点
     	bool deleteNode(List *node);//删除节点不移动头节点
     	bool deleteNode1(List *node);//删除节点移动头节点
     	int listSize();//长度
     	void printNode();//打印但前的value
     	void freeList();//释放链表
      private:
     	int value;
      	List *head;
      	List *next;
      };
      bool List::deleteNode(List *node)
      {
     	if (node == NULL)
      	{
     		std:cout << "node is NULL" << std::endl;
     		return false;
      	}
     	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return false;
      	}
     	//如果node等于head
     	if (head == node)
      	{
      		head = head->next;
      	}
      	List *p = head;
     	while (p->next != NULL)
      	{
     		if (p->next == node)
      		{
      			p->next = p->next->next;
     			return true;
      		}
      		p = p->next;
      	}
     	return false;
      }
      bool List::deleteNode1(List *node)
      {
     	if (node == NULL)
      	{
     		std:cout << "node is NULL" << std::endl;
     		return false;
      	}
     	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return false;
      	}
     	//如果node等于head
     	if (head == node)
      	{
      		head = head->next;
      	}
      	List *p = head;
     	while (head->next != NULL)
      	{
     		if (head->next == node)
      		{
      			head->next = head->next->next;
     			std::cout << "delete node success head->value" << head->value << std::endl;
     			//这里要记得把头节点的指针移动最后还原,这里的头节点是保存在这个类里面,改变了就是改变了
     			//如果这里是把head作为参数传递,最后head会被销毁那么不需要移动头指针
      			head = p;
     			return true;
      		}
     		//注意,这里由于head是成员变量,改变了就是改变了,所以需要最后重新指定
      		head = head->next;
      	}
     	std::cout << "delete node fail head->value" << head->value << std::endl;
     	//这里要记得把头节点的指针移动最后还原,这里的头节点是保存在这个类里面,改变了就是改变了
     	//如果这里是把head作为参数传递,最后head会被销毁那么不需要移动头指针
      	head = p;
     	return false;
      }
      List::List()
      {
      	value = 0;
      	head = NULL;
      	next = NULL;
      }
      List::~List()
      {
     	delete head;
     	delete next;
      }
      List* List::createNode(int value)
      {
      	List *list = NULL;
     	list = new List();
     	if (list)
      	{
     		list->value = value;
     		return list;
      	}
     	return NULL;
      }
      bool List::insertNode(List *node)
      {
      	node->next = head;
      	head = node;
     	return true;
      }
      void List::printList()
      {	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return;
      	}
      	List *p = head;
     	while (p != NULL)
      	{
     		std::cout << p->value << std::endl;
      		p = p->next;
      	}
     	return;
      }
      void List::printNode()
      {
     	std::cout << value << std::endl;
      }
      int List::listSize()
      {
     	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return 0;
      	}
     	int len = 0;
      	List *p = head;
     	while (p != NULL)
      	{
      		p = p->next;
      		++len;
      	}
     	return len;
      }
      void List::freeList()
      {
     	if (head == NULL)
      	{
     		std::cout << "head is NULL" << std::endl;
     		return;
      	}
      	List *p;
     	while (head != NULL)
      	{
      		p = head;
      		head = head->next;
     		free(p);
      	}
      }
      int main()
      {
      	List list;
      	List *list1 = list.createNode(5);
     	list.insertNode(list1);
      	List *list2 = list.createNode(6);
     	list.insertNode(list2);
      	List *list3 = list.createNode(1);
     	list.insertNode(list3);
      	List *list4 = list.createNode(3);
     	list.insertNode(list4);
      	List *list5 = list.createNode(2);
     	list.insertNode(list5);
     	list.printList();
     	std::cout << "list size is " << list.listSize() << std::endl;
     	std::cout << "-----------开始删除节点值为3的节点" << std::endl;
     	list.deleteNode1(list4);
     	list.printList();
     	std::cout << "list size is " << list.listSize() << std::endl;
     	list.freeList();
     	list.printList();
     	return 0;
      }
  
 

3 运行结果

      2
      3
      1
      6
      5
      list size is 5
      -----------开始删除节点值为3的节点
      delete node success head->value2
      2
      1
      6
      5
      list size is 4
      head is NULL
  
 

4 总结

很明显用C语言实现，我们习惯在外面搞个头结点，然后用C++实现，我们直接在类的里面放一个head指针，然后我们在增加节点的时候我们会把head进行移动，放在最前面，所以后面的 便利和删除操作等最好是不要动head的位置了，因为head动了，下次便利就有问题，如果删除函数移动了head，我们最后需要复原head

比如我们的头指针尽量不要移动，我们可以用一个指针变量来保存这个head指针，然后我们移动保存的指针变量，同时把保存的指针变量在一些情况下改变下一个指向的指针，那么我们下次便利head也是生效的，这样保证了头指针不被污染

比如下面的例子

      #include <stdio.h>
      void change(char *a)
      {
      	*(a + 1) = 's';
      }
      int main()
      {
     	char value[10] = "chenyu";
      	change(value);
     	printf("value is %s\n", value);
     	return 0;
      }
      #include <stdio.h>
      void change(char *a)
      {
     	char *p = a;
      	*(p + 1) = 's';
      }
      int main()
      {
     	char value[10] = "chenyu";
      	change(value);
     	printf("value is %s\n", value);
     	return 0;
      }
  
 

其实最后的结果都是一样，csenyu

头指针是指向这块内存的地址，如果我们用指针变量保存了，然后这个指针变量也指向了这里，用指针变量去操作后，然后头指针也是指向这里，后面数据的指向也会改变

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/86516967