單鏈表反轉：詳細解析與代碼實現
在數據結構的學習過程中，鏈表是一個非常重要且有趣的部分，而單鏈表的反轉操作更是常考的基礎知識點。今天就來和大家詳細講講如何實現單鏈表的反轉，并通過代碼示例來加深理解呀。
題目
給定單鏈表的頭節點?head?，請反轉鏈表，并返回反轉后的鏈表的頭節點。
思路分析
要反轉單鏈表，核心思路就是改變鏈表節點中指針的指向方向。我們可以想象成把原來依次相連的節點，逐個 “掉頭”，讓它們按照相反的順序重新連接起來。
為了實現這個過程，我們采用迭代的方法，借助幾個指針來幫忙操作：
- prev 指針：這個指針一開始初始化為?
NULL，它的作用是始終指向當前節點的前一個節點。在反轉的過程中，它相當于一個 “錨點”，讓當前節點能夠指向它，從而改變鏈表的連接方向。 - curr 指針：初始化為鏈表的頭節點?
head，它代表著我們當前正在處理的節點。在每一輪循環中，我們都會對這個節點進行操作，改變它的?next?指針指向。 - nextTemp 指針：它用于臨時保存當前節點的下一個節點。為什么要這么做呢？因為一旦我們改變了當前節點?
curr?的?next?指針指向（讓它指向?prev），如果不提前保存下一個節點的信息，那就會丟失后續鏈表的連接情況，導致鏈表斷裂呀。
整個反轉過程就是通過不斷地循環，在每一輪循環中完成以下幾個關鍵步驟：
- 首先，使用?
nextTemp?保存?curr?節點的下一個節點，也就是執行?nextTemp = curr->next;?這一步，確保后續鏈表不會丟失。 - 接著，把當前節點?
curr?的?next?指針指向它前面的節點?prev，即?curr->next = prev;，這一步就是真正改變鏈表連接方向，實現 “反轉” 的關鍵操作哦。 - 然后，更新?
prev?指針，讓它指向當前節點?curr，執行?prev = curr;，為下一輪循環做準備，因為下一輪循環中，當前節點就變成了之前保存的?nextTemp?所指向的節點了，而此時的?prev?就要相應跟上呀。 - 最后，更新?
curr?指針，讓它指向之前保存的下一個節點?nextTemp，也就是?curr = nextTemp;，這樣就可以進入下一輪循環，繼續處理鏈表中的下一個節點啦。
當循環結束，也就是?curr?遍歷到原鏈表的末尾（即?curr?變為?NULL）時，prev?指針就正好指向了反轉后鏈表的頭節點啦，我們最后返回這個?prev?就大功告成咯。
代碼實現
下面就是使用 C 語言實現單鏈表反轉的完整代碼啦：
#include <stdio.h>
#include <stdlib.h>// 單鏈表節點結構體定義
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode {int val;struct ListNode *next;
};// 創建單鏈表節點的函數
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));if (newNode == NULL) {printf("內存分配失敗！\n");return NULL;}newNode->val = val;newNode->next = NULL;return newNode;
}// 向鏈表末尾插入節點的函數
void insertNode(struct ListNode** head, int val) {struct ListNode* newNode = createNode(val);if (*head == NULL) {*head = newNode;} else {struct ListNode* temp = *head;while (temp->next!= NULL) {temp = temp->next;}temp->next = newNode;}
}// 打印單鏈表的函數
void printList(struct ListNode* head) {struct ListNode* temp = head;while (temp!= NULL) {printf("%d ", temp->val);temp = temp->next;}printf("\n");
}// 反轉單鏈表的函數
struct ListNode* reverseList(struct ListNode* head) {if (head == NULL) {return head;}struct ListNode *prev = NULL;struct ListNode *curr = head;struct ListNode *nextTemp;while (curr!= NULL) {nextTemp = curr->next;curr->next = prev;prev = curr;curr = nextTemp;}return prev;
}int main() {struct ListNode* head = NULL;// 構建一個簡單的單鏈表，例如1 -> 2 -> 3 -> 4 -> 5insertNode(&head, 1);insertNode(&head, 2);insertNode(&head, 3);insertNode(&head, 4);insertNode(&head, 5);printf("原單鏈表為: ");printList(head);struct ListNode* reversedHead = reverseList(head);printf("反轉后的單鏈表為: ");printList(reversedHead);return 0;
}?
)
