206. Reverse Linked List
1. Description
Reverse a singly linked list.
2. Example
Example 1:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
3. Follow Up
- A linked list can be reversed either iteratively or recursively. Could you implement both?
4. Solutions
My Accepted Solution(Follow Up)
n is the number of nodes in m_head
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// ListNode* reverseList(ListNode* head)
ListNode* reverseList(ListNode *m_head)
{
if(!m_head) return nullptr;
auto lastReversedIter = m_head, firstUnreversedIter = m_head->next;
lastReversedIter->next = nullptr;
while(firstUnreversedIter)
{
auto nextNode = firstUnreversedIter->next;
firstUnreversedIter->next = lastReversedIter;
lastReversedIter = firstUnreversedIter;
firstUnreversedIter = nextNode;
}
return lastReversedIter;
}
};
n is the number of nodes in m_head
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// ListNode* reverseList(ListNode* head)
ListNode* reverseList(ListNode *m_head)
{
if(!m_head || !m_head->next) return m_head;
auto result = reverseList(m_head->next);
m_head->next->next = m_head;
m_head->next = nullptr;
return result;
}
};