题目描述
反转一个单链表。
示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
题目链接：https://leetcode-cn.com/problems/reverse-linked-list/
思路1
使用迭代。要记录3个指针：当前的节点curNode，当前节点的前一个节点preNode（用来反转链表），当前的节点的下一个节点nextNode（防止链表断掉）。反转时，将curNode指向preNode，然后更新这三个指针即可。代码如下：
/**
* 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) {
if(head==nullptr || head->next==nullptr){
return head;
}
ListNode* preNode = nullptr;
ListNode* curNode = head;
ListNode* nextNode = nullptr;
while(curNode!=nullptr){
nextNode = curNode->next;
curNode->next = preNode;
preNode = curNode;
curNode = nextNode;
}
return preNode; // 注意返回的是preNode,因为curNode此时为nullptr
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
思路2
使用递归。首先递归到链表尾，返回链表的尾结点（反转后链表的头结点）。在回溯的过程中反转链表。代码如下：
/**
* 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) {
if(head==nullptr || head->next==nullptr){
return head;
}
ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = nullptr; // 注意要赋值为nullptr
return p;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
由于递归会使用栈，使用栈的规模和链表长度线性相关。
总结
使用迭代反转链表有两个非常有用的性质：1、反转结束后preNode就是反转后链表的头结点；2、反转结束后curNode是反转结束后preNode原先指向的那个节点，。（如果把整个链表分成多段分别翻转，这个性质就非常有用，比如K个一组反转链表），如下图
相关题目
1、反转链表 II：https://leetcode-cn.com/problems/reverse-linked-list-ii/， 题解
2、K个一组反转链表：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/，题解