我们只需顺序遍历一次列表,在原地将它们的指向依次逆转。需要注意的是,当链表本身为空的时候我们直接返回空指针就可。在原地倒转过程中,我们需要维护3个指针,分别指向当前结点cur,原链表的下一个结点nextNode,上一个节点pre,分别初始化为head、nullptr、nullptr。使用一个额外的nextNode是因为每次都要断开一个结点的next指针,所以我们需要一个指针来暂时记住它,否则下次迭代就找不到它了。时间复杂度O(N),因为我们需要遍历每个节点,空间复杂度O(1),只需要用到3个指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr){
return nullptr;
}
ListNode *cur, *pre, *nextnode; //需要nextnode来暂时记住下一个结点
pre = nullptr;
cur = head;
do{
nextnode = cur->next;
cur->next = pre;
pre = cur;
cur = nextnode;
}while(nextnode != nullptr);
return pre;
}
};
由于Python中没有do while循环,所以我们在这里用while,初始化nextnode的时候设为head。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None:
return None
cur, pre, nextNode = head, None, head
while nextNode:
nextNode = cur.next
cur.next = pre
pre = cur
cur = nextNode
return pre
递归方法的空间复杂度为O(N),因为每次调用递归都要重新建一个函数的栈帧,多少个节点就是多少帧。比迭代还要额外考虑回退的时候指针的指向问题。代码参考了官方题解。
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;
}
};
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode-solution-d1k2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。