leetcode206. 反转链表
宋标 Lv5
  2022-04-06 18:21:46 2022-04-06 18:21    

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
图片1

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

示例 2：

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

输入：head = []
输出：[]  

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000  

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

迭代解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *pre = NULL,*temp;
    while(head!=NULL){
        //保存下一个节点
        temp = head->next;
        //指向前一个结点
        head->next = pre;
        //当前结点作为下一趟遍历的前驱结点
        pre = head;
        //恢复节点
        head = temp;
    }
    return pre;
}

递归解法
因为反转后需要将反转后的头节点返回出去，我这里用了临时变量进行了存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct ListNode* reverseListRecursiveDo(struct ListNode* head,struct ListNode** root){
    if(head==NULL || head->next==NULL){
        *root = head;
        return head;
   }
   reverseListRecursiveDo(head->next,root)->next = head;
   //第一个结点反转后的next指针应该指向NULL，避免回路
   head->next = NULL;
   return head;
}

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* root = (struct ListNode*)malloc(sizeof(struct ListNode));
    reverseListRecursiveDo(head,&root);
    return root;
}

算法优化，不需要临时变量

1
2
3
4
5
6
7
8
9
10
11
12
13
struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL || head->next==NULL){
        return head;
    }
    //反转后的头节点
    struct ListNode* reverseHead = reverseList(head->next);
    //关键思路
    //假设存在链表：n1->n2->n3->n4->NULL,那么n3->n4的反转可以写成n3->next->next=n3;
    head->next->next = head;
    //n1指向NULL,避免回路
    head->next = NULL;
    return reverseHead;
}
 评论