题目难度：《简单》
（1）题目描述
给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
示例1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例2：
输入：head = [1,2]
输出：[2,1]
示例3：
输入：head = [ ]
输出：[ ]
LeetCode链接：206. 反转链表
（2）解题思路
1）解法1：调整节点指针的方向
- 步骤
- 定义一个指针 cur，用来遍历链表
- 定义一个指针 prev，保存 cur 的上一个节点的位置，初始指向 NULL
- 定义一个指针 next，保存 cur 的下一个节点的位置，用来迭代
- 通过 prev 和 cur 来调整每个节点指针的方向，next 进行迭代
- 最后返回头节点指针 head 即可
- 代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//解题思路：把链表中所有节点的next指针指向反转
struct ListNode* prev = NULL; //保存cur的上一个节点的位置
struct ListNode* cur = head; //遍历链表
while(cur != NULL)
{
struct ListNode* next = cur->next; //保存cur的下一个节点位置
cur->next = prev; //调整当前节点next指针的方向
prev = cur;
cur = next;
}
head = prev; //更新头节点
return head;
}
2）解法2：头插法
- 然后把链表中的所有节点依次头插到一个新链表中，相当于反转了原链表
- 定义一个指针 cur，用来遍历原链表
- 定义一个指针 next，保存 cur 的下一个节点的位置
- 定义一个指针 newhead，指向新链表的头节点
- 动图演示
- 代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
//解题思路：把链表中的所有节点依次头插到一个新链表中，相当于反转了原链表
//当链表为空或链表只有一个节点时
if(head == NULL || head->next == NULL)
{
return head;
}
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while(cur)
{
//保存cur当前所在节点的下一个节点的位置
struct ListNode* next = cur->next;
cur->next = newhead; //开始头插
newhead = cur; //更新头节点
cur = next; //cur指向下一个待插入的节点
}
return newhead;
}
大家快去动手练习一下吧！