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

#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; 
}

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