【LeetCode】反转链表（C语言）| 动图演示，超详细哦~_翻转链表动画演示

题目难度：《简单》

（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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

大家快去动手练习一下吧！