188 lines
4.1 KiB
Markdown
188 lines
4.1 KiB
Markdown
# Leetcode Reverse-Linked-List
|
|
|
|
#### 2022-06-15 22:07
|
|
|
|
---
|
|
|
|
##### Algorithms:
|
|
|
|
#algorithm #recursion #iteration
|
|
|
|
##### Data structures:
|
|
|
|
#DS #linked_list
|
|
|
|
##### Difficulty:
|
|
|
|
#leetcode #coding_problem #difficulty_medium
|
|
|
|
##### Lists:
|
|
|
|
#CS_list_need_understanding #CS_list_need_practicing
|
|
|
|
##### Revisions:
|
|
|
|
2022-07-02
|
|
2022-09-20
|
|
|
|
##### Related topics:
|
|
|
|
##### Links:
|
|
|
|
- [Link to problem](https://leetcode.com/problems/reverse-linked-list/)
|
|
|
|
---
|
|
|
|
### Problem
|
|
|
|
Given the `head` of a singly linked list, reverse the list, and return _the reversed list_.
|
|
|
|
#### Examples
|
|
|
|
**Example 1:**
|
|
|
|
|
|
|
|
```markdown
|
|
**Input:** head = [1,2,3,4,5]
|
|
**Output:** [5,4,3,2,1]
|
|
```
|
|
|
|
**Example 2:**
|
|
|
|
|
|
|
|
```markdown
|
|
**Input:** head = [1,2]
|
|
**Output:** [2,1]
|
|
```
|
|
|
|
**Example 3:**
|
|
|
|
```markdown
|
|
**Input:** head = []
|
|
**Output:** []
|
|
```
|
|
|
|
#### Constraints
|
|
|
|
- The number of nodes in the list is the range `[0, 5000]`.
|
|
- `-5000 <= Node.val <= 5000`
|
|
|
|
### Thoughts
|
|
|
|
Many ways to implement this. from slow but easy ones, to
|
|
fast but hard ones:
|
|
|
|
#### Easy way:
|
|
|
|
I thought a slow O(n ^ 2) hybrid solution, while there are better algorithms, using in-place insert, or recursion.
|
|
|
|
#### Fast way:
|
|
|
|
#### Recursion
|
|
|
|
The in place insert is easier to understand, and simple to implement, using a very clever trick.
|
|
|
|
> [!summary] My thoughts on the recursion algorithm
|
|
>
|
|
> #### How was that implemented?
|
|
>
|
|
> The recursion algorithm takes the advantage of the fact that when you change the node's next properties or nodes after that, the node before still points to the same node, so when every node after **tmp** is reversed, simply move **tmp** after **tmp->next**, which now points to the tail of reversed list
|
|
>
|
|
> #### Why return the last element of the original list?
|
|
>
|
|
> It returns the last element in the original list to make sure you are always returning the head of the reversed array, since for any reversed list, the last one comes first.
|
|
> **The only recursive part is returning the _tail node_.**
|
|
|
|
##### Iteration
|
|
|
|
The iteration method use two pointers:
|
|
|
|
- one that points to the new head, as an anchor
|
|
- The other one points to nodes we need to iterate over:
|
|
|
|
The iterator **has** to be pointing to head, and use
|
|
`cur->next` instead of directly using cur, otherwise will
|
|
lead to strange loops or bugs.
|
|
|
|
The pointer moves by `cur->next = cur->next->next`, it
|
|
represents the head element.
|
|
|
|
### Solution
|
|
|
|
I've referred to this guy: https://leetcode.com/problems/reverse-linked-list/discuss/58130/C%2B%2B-Iterative-and-Recursive
|
|
|
|
Insertion, iteration
|
|
|
|
```cpp
|
|
class Solution {
|
|
public:
|
|
ListNode *reverseList(ListNode *head) {
|
|
ListNode *pre = new ListNode(0), *cur = head;
|
|
// pre is before head, and insert any element after pre.
|
|
pre->next = head;
|
|
while (cur && cur->next) {
|
|
// temp points to head
|
|
ListNode *temp = pre->next;
|
|
// Move cur->next after pre.
|
|
pre->next = cur->next;
|
|
// Fix pointers, because cur->next is unchanged when changing position.
|
|
// This part is important, must use cur->next.
|
|
cur->next = cur->next->next;
|
|
pre->next->next = temp;
|
|
}
|
|
return pre->next;
|
|
}
|
|
};
|
|
```
|
|
|
|
Recursion:
|
|
|
|
2022-09-20 version
|
|
```cpp
|
|
class Solution {
|
|
public:
|
|
ListNode *reverseList(ListNode *head) {
|
|
// Recursion
|
|
|
|
// Base case: no need to reverse:
|
|
if (head == nullptr || head->next == nullptr) {
|
|
return head;
|
|
}
|
|
|
|
// assuming we have the head of reversed sub-list
|
|
// head->next still points to next one in the unchanged order,
|
|
// or the tail of the reversed list
|
|
auto newHead = reverseList(head->next);
|
|
|
|
head->next->next = head;
|
|
head->next = nullptr;
|
|
|
|
return newHead;
|
|
}
|
|
};
|
|
```
|
|
|
|
```cpp
|
|
class Solution {
|
|
public:
|
|
ListNode *reverseList(ListNode *head) {
|
|
// Recursion
|
|
if (head == nullptr || head->next == nullptr) {
|
|
// base case: return the tail
|
|
return head;
|
|
}
|
|
|
|
// have to call itself before modifying, since head->next will point to
|
|
// nullptr
|
|
ListNode *newHead = reverseList(head->next);
|
|
|
|
head->next->next = head;
|
|
head->next = nullptr;
|
|
|
|
return newHead;
|
|
}
|
|
};
|
|
```
|