Problem: 206. 反转链表
题目描述
思路
迭代写法:
1.定义前驱节点pre初始指向null,指针cur指向head;
2.遍历链表(退出条件是cur为空):2.1.定义一个nextP指针指向当前节点的下一个节点;
2.2.让cur的next指针指向pre指针;
2.3.使pre指向cur指针;
2.4.使cur指针指向nextP指针,并最后返回pre指针
递归写法:
(具体实现看代码实际操作!!!)由于我么需要翻转单链表,所以我们用递归去实现则需要在归的过程中去实现翻转操作
复杂度
时间复杂度:
O ( n ) O(n) O(n);其中 n n n为链表的长度
空间复杂度:
O ( n ) O(n) O(n)
Code
/**
class Solution {
public:
/**
* Iteration
*
* @param head The head node of linked list
* @return ListNode*
*/
ListNode* reverseList(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* nextP = cur -> next;
cur -> next = pre;
pre = cur;
cur = nextP;
}
return pre;
}
};
class Solution {
public:
/**
* Recursion
*
* @param head The head node of linked list
* @return ListNode*
*/
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head -> next == nullptr) {
return head;
}
ListNode* res = reverseList(head -> next);
head -> next -> next = head;
head -> next = nullptr;
return res;
}
};