链表的基本操作

• 节点结构体:

typedef struct Node {
  int element;
  struct Node* next;
} node;

• 创建一个链表:

node* createList() {
  node* head = (node*)malloc(sizeof(node));
  head->element = 0;
  head->next = NULL;
  return head;
}

把一个空的节点当作链表的头会让下面的操作更加容易实现.

• 插入:

void insert(int x, node* list) {
  node* current = (node*)malloc(sizeof(node));
  current->element = x;
  current->next = list->next;
  list->next = current;
}

若不是把一个空的节点当作链表的头,则我们要传进的参数将会是
(int x, node** list),而现在我们只需要修改list->next就可以把新增节点插入链表头.

• 删除:

void del(int x, node* list) {
  node* ptr = list;

  // 找到要删除节点的前一个节点
  while (ptr->next != NULL && ptr->next->element != x)
    ptr = ptr->next;

  // 如果找不到则返回
  if (ptr->next == NULL)
    return;

  // 找到后删除
  node* current = ptr->next;
  ptr->next = current->next;
  free(current);
}

• 查找:

node* find(int x, node* list) {
  node* ptr = list->next;

  while (ptr != NULL && ptr->element != x)
    ptr = ptr->next;

  return ptr;
}

• 逆序

void reverse(node* list) {
  node* head = list->next;
  node* temp = NULL;
  
  // 链表不为空
  if (head != NULL) {
    // 第二个node
    node* current = head->next;
    
    // 第一个node将作为尾节点,故指向NULL
    head->next = NULL;
    
    while (current != NULL) {
      temp = current->next;
      current->next = list->next;
      list->next = current;
      current = temp;
    }
  }
}