单链表反转

单链表的数据结构如下图所示：

假如有一个单链表是：1->2->3->4->NULL，那么经过反转后就变为：4->3->2->1->NULL。

具体代码实现

• 定义单链表

  struct Node{
      int data;
      struct Node *next;
  };

• 构造单链表

  构造单链表的思想就是：创建一个节点，然后判断是否有头结点，如果有，就将当前节点的next指向新创建的节点，然后将当前节点向后移动；如果没有，就将头结点和当前节点都赋值为新创建的节点。

  struct Node* constructList(void) {
      // 定义头部节点
      struct Node *head = NULL;
      // 记录当前结点
      struct Node *cur = NULL;
      
      for (int i = 1; i < 5; i++) {
          struct Node *node = malloc(sizeof(struct Node));
          node->data = i;
          node->next = NULL;
          
          if (head == NULL) {
              // 头结点为空，当前节点为头结点
              head = node;
          } else {
              // 当前节点的 next 为新节点
              cur->next = node;
          }
          // 设置当前节点
          cur = node;
      }
      return head;
  }

• 链表反转（头插法）

  头插法需要我们定义一个新的头结点作为新的链表，然后利用头插法，将原来的链表的每一个节点取出来，然后去新的链表里面做头插法，这样就可以反转了，这里需要一个新的头结点，和遍历原来链表的一个p指针。

  struct Node* reverseList(struct Node *head) {
      // 定义一个遍历指针，并初始化为头结点
      struct Node *p = head;
      // 反转后的头结点
      struct Node *newH = NULL;
      // 遍历链表
      while (p != NULL) {
          // 记录下一个节点
          struct Node *temp = p->next;
          // 当前节点的 next 指向新链表头部
          p->next = newH;
          // 更改新链表头部为当前节点
          newH = p;
          // 移动 p 指针
          p = temp;
      }
      return newH;
  }

• 打印链表数据

  最后，我们打印下链表数据，看下效果。

  void printList(struct Node *node) {
      struct Node *temp = node;
      while (temp != NULL) {
          printf("node is %d \n", temp->data);
          temp = temp->next;
      }
  }

打赏