Leetcode---反转链表_输入一个链表,对其进行反转,返回反转后的链表头节点

反转链表操作：
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000

1、 双指针法
时间复杂度: O(N) 需要的操作为链表长度
空间复杂度：O(1) 消耗常数大小的内存空间
解题思路：首先在循环内遍历链表，循环结束的条件就是当前的指针为空指针；使用一个中间变量（temp）存储当前指针指向的下一个链表地址；然后将当前指针指向链表中的下一个链表地址进行修改，改为pre（pre指针总是指向当前链表的上一个链表地址，若当前链表指针为head，则pre为空指针）；移动当前指针，使其指向下一个链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        /*
        双指针做法，时间复杂度O(n), 空间复杂度O(1)
        
        */

        ListNode* pre = nullptr;
        while(head != nullptr)
        {
            ListNode* 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
17
18
19
20
21
22
23
24
25
26
27
28

关于最后为什么 return pre：
循环结束后，此时head应当是一个空指针了，pre是反转后链表的表头指针。

执行结果：

2、 递归法

该方法对于我这样的小白来说还是比较难理解，递归不难，主要是回溯的过程有点想不明白；
递归的作用就是遍历到最后一个节点，然后再回溯中，将当前节点指向的next，修改为其前一个节点
。这里比较绕的就是两个指针分别为：当前节点、当前节点的next，在回溯中的具体做法为，将当前节点的next修改为指向当前节点，然后进入下一层回溯。
在最后一层返回res，res存储的是最后一个节点的地址。因此在程序中不对res进行修改，每次回溯均返回这个res，最后输出的就是反转后的链表的表头。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recur(head, nullptr);
    }

private:
    ListNode* recur(ListNode*cur, ListNode*pre)
    {
        if(cur == nullptr) return pre;
        ListNode* res = recur(cur->next, cur);
        cur->next = pre;
        return res;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

执行效果：