链表基础3——单链表的逆置

链表的定义

#include <stdio.h>  
#include <stdlib.h>  typedef struct Node {  int data;  struct Node* next;  
} Node;  Node* createNode(int data) {  Node* newNode = (Node*)malloc(sizeof(Node));  if (!newNode) {  return NULL;  }  newNode->data = data;  newNode->next = NULL;  return newNode;  
}  void printList(Node* head) {  Node* current = head;  while (current != NULL) {  printf("%d ", current->data);  current = current->next;  }  printf("\n");  
}  

不带头结点的单向不循环链表的逆置

不带头结点的单向不循环链表的逆置方式主要有以下几种：

1. 迭代法：
   这种方法使用一个指针遍历链表，同时使用另一个指针指向当前节点的前一个节点。在遍历过程中，每次都将当前节点的next指针指向前一个节点，从而实现链表的逆置。需要注意的是，在逆置过程中，还需要保存下一个要处理的节点，因为逆置后当前节点的next指针会指向前一个节点，从而失去对下一个节点的引用。

2. 递归法：
   递归法通过递归调用实现链表的逆置。递归的基本思想是：先递归到链表的最后一个节点，然后将该节点的next指针指向它的前一个节点，接着返回前一个节点，继续逆置前面的部分。递归法的好处是代码简洁，但递归深度较大时可能会导致栈溢出。

3. 栈辅助法：
   这种方法利用栈的后进先出特性来实现链表的逆置。首先将链表中的每个节点依次入栈，然后再依次出栈，并将出栈节点的next指针指向它的前一个出栈节点，从而实现链表的逆置。这种方法需要额外的空间来存储栈中的节点。

4. 三指针法：
   这种方法使用三个指针，分别指向当前节点、前一个节点和下一个节点。在遍历过程中，先将当前节点的next指针指向前一个节点，然后移动三个指针，继续处理下一个节点。这种方法与迭代法类似，但使用了更多的指针来简化操作。

每种方法都有其特点和适用场景，可以根据具体需求选择合适的方法来实现链表的逆置。在实际应用中，还需要考虑代码的可读性、健壮性和性能等因素。

迭代法

// 迭代法逆置链表  
void reverseListIterative(Node** head) {  Node* prev = NULL; // prev指向前一个节点，初始化为NULL  Node* current = *head; // current指向当前节点，初始化为头节点  while (current != NULL) {  Node* next = current->next; // next指向下一个节点  current->next = prev; // 将当前节点的next指针指向前一个节点，实现逆置  prev = current; // 将prev移动到当前节点  current = next; // 将current移动到下一个节点  }  *head = prev; // 更新头指针，指向新的头节点（原链表的尾节点）  
}  

逐步分解

 

 

到这里循环就结束了

 到这里彻底完成链表的逆置 

递归法

// 递归法逆置链表  
Node* reverseListRecursive(Node* head) {  // 递归终止条件：当前节点为空或当前节点的下一个节点为空  if (head == NULL || head->next == NULL) {  return head;  }  // 递归调用，逆置剩余部分链表，并返回新的头节点  Node* newHead = reverseListRecursive(head->next);  // 处理当前节点，将其指向原来的前一个节点，实现逆置  head->next->next = head;  head->next = NULL;  // 返回新的头节点  return newHead;  
}// main 函数和其他辅助函数与迭代法相同

递归的思想是将一个大问题分解为若干个更小的子问题来解决。在链表逆置的场景中，我们可以将问题分解为“逆置除头节点外的剩余链表，并将头节点放到逆置后链表的尾部”。

递归函数reverseListRecursive的工作过程如下：

1. 基本情况（递归终止条件）：
   • 如果链表为空（head == NULL），或者链表只有一个节点（head->next == NULL），那么链表已经逆置完成（或者说，无需逆置），直接返回当前头节点。
2. 递归步骤：
   • 假设当前头节点head的下一个节点开始的链表部分（即剩余链表）已经通过递归调用reverseListRecursive(head->next)逆置完成，并返回了新的头节点newHead。
3. 处理当前节点：
   • 在递归调用返回后，newHead指向逆置后链表的头节点。此时，我们需要将当前节点head放到逆置后链表的尾部。
   • 由于head->next现在指向逆置后的链表，我们将head->next->next指向head，这样就将head节点添加到了逆置后链表的尾部。
   • 然后，我们需要将head->next设置为NULL，因为head现在是新链表的最后一个节点。
4. 返回新头节点：
   • 最后，递归函数返回newHead，即逆置后链表的头节点。

这个过程是一个典型的“自底向上”的递归：我们先递归地逆置剩余部分链表，然后再处理当前节点。递归的每一次调用都处理一个更小的子问题，直到到达基本情况（链表为空或只有一个节点）。

以一个简单的例子来说明：

假设链表为 A -> B -> C -> D。

• 递归调用reverseListRecursive(D)，D没有下一个节点，返回D。
• 递归调用reverseListRecursive(C)，它首先递归调用reverseListRecursive(D)得到D，然后将C添加到D的前面，得到D -> C，并返回D作为新头节点。
• 递归调用reverseListRecursive(B)，它首先递归调用reverseListRecursive(C)得到D -> C，然后将B添加到D -> C的前面，得到C -> D -> B，并返回C作为新头节点。
• 最后，reverseListRecursive(A)调用reverseListRecursive(B)得到C -> D -> B，然后将A添加到C -> D -> B的前面，得到B -> C -> D -> A，并返回B作为新头节点。

最终，A -> B -> C -> D被逆置为B -> C -> D -> A。

通过这种方式，递归能够逐步地将整个链表逆置。希望这个解释能够更清楚地说明递归是如何实现链表逆置的。

栈辅助法

typedef struct Node {  int data;  struct Node* next;  
} Node;  typedef struct Stack {  Node* top;  
} Stack;  void push(Stack* stack, Node* node) {  node->next = stack->top;  stack->top = node;  
}  Node* pop(Stack* stack) {  if (stack->top == NULL) {  return NULL;  }  Node* node = stack->top;  stack->top = stack->top->next;  node->next = NULL; // 避免悬挂指针  return node;  
}  bool isEmpty(Stack* stack) {  return stack->top == NULL;  
}  // 栈辅助法逆置链表  
Node* reverseListWithStack(Node* head) {  StackNode* stack = createStack();  Node* dummy = createNode(0); // 创建一个哑节点作为新链表的头节点  Node* tail = dummy; // tail指向新链表的尾节点  // 将原链表的节点依次入栈  while (head != NULL) {  push(&stack, head);  head = head->next;  }  // 将栈中的节点依次出栈并连接到新链表上  while ((head = pop(&stack)) != NULL) {  tail->next = head;  tail = head;  }  // 新链表的尾节点指向NULL  tail->next = NULL;  // 返回新链表的头节点（哑节点的下一个节点）  return dummy->next;  
}  // 辅助函数和main函数与之前相同

三指针法

// 三指针法逆置链表  
Node* reverseListWithThreePointers(Node* head) {  if (head == NULL || head->next == NULL) {  return head;  }  Node* prev = NULL;  Node* current = head;  Node* nextTemp = NULL;  while (current != NULL) {  nextTemp = current->next; // 保存下一个节点  current->next = prev; // 反转当前节点的指针  prev = current; // prev移动到当前节点  current = nextTemp; // current移动到下一个节点  }  return prev; // prev现在指向新的头节点  
}  // ...（其他函数和main函数保持不变） 

 逐步分解

 

测验代码

int main() {  Node* head = createNode(1);  head->next = createNode(2);  head->next->next = createNode(3);  head->next->next->next = createNode(4);  printf("Original List: ");  printList(head);  reverseListIterative(&head);  printf("Reversed List: ");  printList(head);  // 释放链表内存  Node* temp;  while (head != NULL) {  temp = head;  head = head->next;  free(temp);  }  return 0;  
}

带头结点的单向不循环链表的逆置

对于带头结点的单向不循环链表的逆置，我们依然可以使用递归或迭代的方法。

由于头结点通常不存储数据，而是作为链表的起始标识和方便操作，逆置链表时通常不会涉及头结点的变动。

以下，我将分别解释递归和迭代如何对带头结点的单向不循环链表进行逆置。

递归法

在递归法中，我们关注的是链表的当前节点和它的下一个节点。递归的基本思想是：先递归处理子问题（逆置剩余链表），然后处理当前节点。

 typedef struct ListNode {  int val;  struct ListNode *next;  } ListNode;  ListNode* reverseListRecursive(ListNode* head) {  // 如果链表为空或只有一个节点（即头结点后面没有节点），则无需逆置  if (head == NULL || head->next == NULL) {  return head;  }  // 递归调用，逆置头结点后面的链表部分，并返回新的头节点  ListNode* newHead = reverseListRecursive(head->next);  // 处理当前头结点，将其next指针指向它的前一个节点  head->next->next = head;  // 将当前头结点的next指针置为NULL，因为它现在是新链表的最后一个节点  head->next = NULL;  // 返回新的头节点  return newHead;  } 

在上面的代码中，递归函数reverseListRecursive接收一个指向头结点的指针head，并返回逆置后链表的新的头结点。注意，由于带头结点，我们不会改变头结点的位置，只会改变头结点后面链表的逆置。

迭代法

迭代法则是通过循环和指针操作来逐步逆置链表。对于带头结点的链表，迭代法通常更加直观和易于理解。

 ListNode* reverseListIterative(ListNode* head) {  if (head == NULL || head->next == NULL) {  return head;  }  ListNode* prev = head; // prev初始指向头结点  ListNode* curr = head->next; // curr初始指向头结点后的第一个节点  // 当curr不为空时，持续进行逆置操作  while (curr != NULL) {  ListNode* nextTemp = curr->next; // 保存curr的下一个节点  curr->next = prev; // 将curr的next指针指向前一个节点，实现逆置  prev = curr; // prev向后移动一位  curr = nextTemp; // curr向后移动一位  }  // 最后将头结点的next指向新的头节点  head->next = prev;  // 返回新的头节点  return prev;  } 

在这个迭代法中，我们使用三个指针：prev始终指向当前逆置部分的最后一个节点，curr指向待逆置的当前节点，nextTemp用于临时存储curr的下一个节点，以便在逆置当前节点后能够继续迭代。

无论是递归还是迭代法，带头结点的单向不循环链表的逆置操作的关键都在于逐步改变节点的next指针的指向，从而实现链表的逆置。

迭代法通常比递归法在空间效率上更优，因为它不需要递归调用栈的空间。而在时间效率上，两者在平均和最坏情况下通常都是O(n)，其中n是链表的长度。