【算法】反转链表的四种方法(C语言)
文章目录
- 方法一 原地反转
- 方法二 迭代
- 方法三 递归
- 方法四 新建链表法
206. 反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2] 输出:[2,1]
示例 3:
输入:head = [] 输出:[]
提示:
- 链表中节点的数目范围是 [0, 5000]
- -5000 next:1.连:第一步先将pre所在节点和cur->next所在节点连接起来,将当前节点 cur 从链表中移除,并把链表连接起来。
cur->next = head;2.掉:将cur的next指向head,将cur插入到head的前面,以便将其放置到链表的前面,成为新的头节点。
head = cur;3.接:更新head,使其指向当前的cur
cur = pre->next;4.移:更新cur,移动到下一个待反转的节点
struct ListNode* reverseList(struct ListNode* head) { if (head == NULL) { return head; } struct ListNode* cur = head->next; struct ListNode* pre = head; while (cur) { pre->next = cur->next; cur->next = head; head = cur; cur = pre->next; } return head; }
方法二 迭代
temp保存cur的下一个节点,以防止反转时丢失链表信息。
cur->next = pre;将cur的下一个指针指向pre,实现反转。
更新pre为当前的cur,为下一次迭代做准备。
更新cur为保存的下一个节点temp,继续迭代。
通过不断改变指针的指向将链表进行反转。pre充当新链表的头节点,当cur为NULL循环停止,返回pre
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* pre = NULL; struct ListNode* cur = head; while (cur != NULL) { struct ListNode* temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; }
方法三 递归
我们可以通过迭代的方法来得到递归方法
观察reverse函数,
函数声明中pre指针指向的为NULL,cur指针指向的为head,正如递归中声明并初始化的pre和cur指针
递归结束条件为cur为NULL,返回pre
同样temp保存cur的下一个节点,以防止反转时丢失链表信息。
然后进行反转cur->next = pre;
pre 为当前已反转部分的头节点,cur为当前待反转的节点。
然后调用递归,将cur作为新的pre传入下一层,将temp作为新的cur传入下一层。
实现了链表的递归反转
struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur) { if (!cur){ return pre; } struct ListNode* temp = cur->next; cur->next = pre; //将cur作为pre传入下一层 //将temp作为cur传入下一层,改变其指针指向当前cur return reverse(cur, temp); } struct ListNode* reverseList(struct ListNode* head) { return reverse(NULL, head); }
方法四 新建链表法
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = head->val;
新建一个链表,并初始化
newNode->next = newHead;将新节点插入到新链表的头部
newHead = newNode;
head = head->next;
遍历原链表,使用头插法新建链表,并不断移动newHead指针,当原链表头指针指向NULL最终返回newHead
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newHead = NULL; while (head) { // 创建一个新节点 struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode)); newNode->val = head->val; // 将新节点插入到新链表的头部 newNode->next = newHead; newHead = newNode; // 移动到原链表的下一个节点 head = head->next; } return newHead; }
感谢您的阅读