Reverse Linked List - CS Interviewing

linkedlist

recursion

# Reverse Linked List

## Difficulty
Easy

## Tags
`linked list`, `recursion`

## Problem Statement
Given the head of a singly linked list, reverse the list and return the reversed list's head.

## Constraints
- The number of nodes in the list is in the range [0, 5000].
- -5000 ≤ Node.val ≤ 5000
- Can be solved iteratively or recursively.

## Signatures
### Python
```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reverse_list(head: ListNode) -> ListNode:
    pass
```

### Java
```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode reverse_list(ListNode head) {
        return null;
    }
}
```

### Csharp
```csharp
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode reverse_list(ListNode head) {
        throw new NotImplementedException();
    }
}
```

### Cpp
```cpp
/**
 * 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* reverse_list(ListNode* head) {
        
    }
};
```

### C
```c
ListNode* reverse_list(ListNode* head) {
    
}
```

### Ruby
```ruby
def reverse_list(head)
    
end
```

### Perl
```perl
sub reverse_list {
    my ($self, @args) = @_;
    
}
```

### Scala
```scala
object Solution {
    def reverse_list(head: ListNode): ListNode = {
        
    }
}
```

### Haskell
```haskell
reverse_list :: ... -> ...
reverse_list args = undefined
```

### Clojure
```clojure
(defn reverse_list [head]
  )
```

### Scheme
```scheme
(define (reverse_list head)
  )
```

## Examples
### Example 1
**Input:**
```
head = [1, 2, 3, 4, 5]
```
**Output:**
```
[5, 4, 3, 2, 1]
```
**Explanation:** The list 1→2→3→4→5 becomes 5→4→3→2→1.

### Example 2
**Input:**
```
head = [1, 2]
```
**Output:**
```
[2, 1]
```

### Example 3
**Input:**
```
head = []
```
**Output:**
```
[]
```
**Explanation:** Empty list remains empty.

## Hints
### Iterative Approach
1. Use three pointers: `prev`, `curr`, `next_temp`.
2. Initialize `prev = None`, `curr = head`.
3. For each node, save `next_temp = curr.next`, then set `curr.next = prev`.
4. Move `prev = curr`, `curr = next_temp`.
5. Return `prev` when done.

### Recursive Approach
1. Base case: if head is None or head.next is None, return head.
2. Recursively reverse the rest: `new_head = reverse(head.next)`.
3. Set `head.next.next = head` and `head.next = None`.
4. Return `new_head`.

Please log in to view the solution editor and submit code.