反转链表（C语言）

题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：
输入：head = []
输出：[]

题目来源（力扣）：反转链表

解法一

基本思路：
反转指针的指向，即从前往后地把链表节点指针的指向反转。

struct ListNode* reverseList(struct ListNode* head){
   struct ListNode* prev = NULL;
   struct ListNode* cur = head;
   while (cur)
   {
       struct ListNode* next = cur->next; //保存好cur下一次要指向的节点
       cur->next = prev;
       prev = cur;
       cur = next;
   }

   return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

解法二

基本思路：
把原链表节点一个一个地取下来重新进行头插，最后的结果也是反转了链表。

struct ListNode* reverseList(struct ListNode* head){
   struct ListNode* cur = head;
   struct ListNode* newhead = NULL;
   while (cur)
   { 
       struct ListNode* next = cur->next;  //头插前先用next保存cur下次要指向的节点
       //头插
       cur->next = newhead;
       newhead = cur;
       cur = next;
   }
   return newhead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

本专栏
有关链表的题目

其它专栏
有关数组的题目