翻转链表,非常经典的一道题目,不难,但是细节问题需要注意,这里用三种方法来做,前两种是迭代,最后一种是递归,个人认为第一种方法最好.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both
方法一:利用 pre 指针,追个翻转节点
该方法从头到尾遍历链表,逐个翻转节点就行,易错点在于返回值一定是 pre,而且 pre 的初始化要是 null,这里就是反转之后链表的末尾,第一次我就写成了 cur
代码如下:
时间复杂度:O(n)
/**
* 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 || !head - >next) return head;
ListNode * pre = nullptr,
*cur = head; //初始化一样很重要
while (cur) {
ListNode * t = cur - >next;
cur - >next = pre;
pre = cur;
cur = t;
}
//return cur;
return pre;
}
};
空间复杂度:O(1)
方法二:
设置虚拟头结点,每次在虚拟节点之后插入 cur 节点,最后直接返回 dummy->next
时间复杂度:O(n)
/**
* 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 || !head->next)
return head;
ListNode *dummy = new ListNode(-1);
ListNode *pre = dummy;
ListNode *cur = head;
dummy->next = head;
while (cur && cur->next)
{
ListNode *t = cur->next;
cur->next = t->next;
t->next = pre->next; //这里注意 一定不要写成t->next = cur;这么做只有第一次交换是对的之后都不对
pre->next = t;
}
return dummy->next;
}
};
空间复杂度:O(1)
方法三:递归的方法,每次翻转当前节点之后的所有节点,注意递归之后的操作以及最后的终止条件的确定
时间复杂度:O(n)
/**
* 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 || !head->next)
return head;
ListNode *newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
空间复杂度:O(n)
参考连接:
https://leetcode.com/problems/reverse-linked-list/solution/
https://leetcode.com/problems/reverse-linked-list/discuss/58130
来源: http://www.bubuko.com/infodetail-2459517.html