# Reverse Linked List
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/reverse-linked-list
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Linked List
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Deloitte](https://scaleengineer.com/companies/deloitte), [Expedia](https://scaleengineer.com/companies/expedia), [Google](https://scaleengineer.com/companies/google), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Luxoft](https://scaleengineer.com/companies/luxoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Ozon](https://scaleengineer.com/companies/ozon), [PayPal](https://scaleengineer.com/companies/paypal), [Paytm](https://scaleengineer.com/companies/paytm), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Siemens](https://scaleengineer.com/companies/siemens), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Visa](https://scaleengineer.com/companies/visa), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [tcs](https://scaleengineer.com/companies/tcs), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Tesla](https://scaleengineer.com/companies/tesla), [Zynga](https://scaleengineer.com/companies/zynga), [Snap](https://scaleengineer.com/companies/snap), [Zenefits](https://scaleengineer.com/companies/zenefits), [X](https://scaleengineer.com/companies/x), [NetApp](https://scaleengineer.com/companies/netapp)
---
## Problem
Given the `head` of a singly linked list, reverse the list, and return _the reversed list_.

**Example 1:**

![](https://assets.glich.co/dsa/reverse-linked-list/image0.jpg) 

**Input:** head = [1,2,3,4,5]
**Output:** [5,4,3,2,1]

**Example 2:**

![](https://assets.glich.co/dsa/reverse-linked-list/image1.jpg) 

**Input:** head = [1,2]
**Output:** [2,1]

**Example 3:**

**Input:** head = []
**Output:** []

**Constraints:**

* The number of nodes in the list is the range `[0, 5000]`.
* `-5000 <= Node.val <= 5000`

**Follow up:** A linked list can be reversed either iteratively or recursively. Could you implement both?

# Approaches
## Recursive Approach
This approach uses recursion to reverse the linked list by recursively reaching the end of the list and then backtracking to reverse the links.
**Time:** O(n) where n is the number of nodes in the linked list - we need to traverse each node once · **Space:** O(n) due to the recursive call stack - we make n recursive calls for n nodes
**Pros:** Clean and elegant solution; Easy to understand the logic; Good for learning recursive thinking
**Cons:** Uses extra space due to recursive call stack; Can cause stack overflow for very large lists; Not as space efficient as iterative approach
### Explanation
The recursive approach works by:
1. First, we need to reach the end of the linked list through recursion
2. As we backtrack, we reverse the links between nodes
3. Finally, we set the head's next to null to complete the reversal

Here's the implementation:
```java
public ListNode reverseList(ListNode head) {
    // Base cases: if head is null or we've reached the last node
    if (head == null || head.next == null) {
        return head;
    }
    
    // Recursively reach the last node
    ListNode reversedList = reverseList(head.next);
    
    // Reverse the link between current node and next node
    head.next.next = head;
    head.next = null;
    
    return reversedList;
}
```

Let's see how it works with example [1,2,3]:
1. First recursive call: head = 1, calls reverseList(2)
2. Second recursive call: head = 2, calls reverseList(3)
3. Third recursive call: head = 3, returns 3 as it's the last node
4. Backtrack to 2: makes 3->2, 2->null
5. Backtrack to 1: makes 2->1, 1->null
6. Final result: 3->2->1->null
### Algorithm
1. Base case: if head is null or head.next is null, return head
2. Recursively call reverseList on head.next until reaching the end
3. For each recursive call during backtracking:
   - Set head.next.next = head (reverse the link)
   - Set head.next = null
4. Return the new head of reversed list

## Iterative Approach
This approach uses three pointers to iteratively traverse the list and reverse the links between nodes. It's more space-efficient than the recursive approach.
**Time:** O(n) where n is the number of nodes in the linked list - we need to traverse each node once · **Space:** O(1) as we only use three pointers regardless of input size
**Pros:** Constant space complexity; No risk of stack overflow; Generally faster than recursive approach; More memory efficient
**Cons:** Slightly more complex to understand at first; Requires keeping track of three pointers; Code might look less elegant than recursive solution
### Explanation
The iterative approach maintains three pointers:
1. prev: points to the previous node (starts as null)
2. curr: points to the current node (starts as head)
3. next: points to the next node (used to maintain the next reference)

Here's the implementation:
```java
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        // Store next node
        ListNode next = curr.next;
        
        // Reverse the link
        curr.next = prev;
        
        // Move prev and curr one step forward
        prev = curr;
        curr = next;
    }
    
    return prev;
}
```

Let's see how it works with example [1,2,3]:
1. Initial state: prev=null, curr=1, next=2
2. First iteration: 1->null, prev=1, curr=2
3. Second iteration: 2->1->null, prev=2, curr=3
4. Third iteration: 3->2->1->null, prev=3, curr=null
5. Return prev as new head
### Algorithm
1. Initialize three pointers: prev=null, curr=head
2. While curr is not null:
   - Store next = curr.next
   - Reverse link: curr.next = prev
   - Move prev = curr
   - Move curr = next
3. Return prev as new head

# Solutions
### 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 ReverseList ( ListNode head ) { ListNode pre = null ; for ( ListNode p = head ; p != null ;) { ListNode t = p . next ; p . next = pre ; pre = p ; p = t ; } return pre ; } }
```

### Java

```java
public class Reverse_Linked_List { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /* 1,2,3,4,5 2,1 prev=2 - 3,4,5 current=3 3,2,1 prev=3 - 4,5 current=4 ... */ // https://leetcode.com/problems/reverse-linked-list/solution/ class Solution_oj_iterative { public ListNode reverseList ( ListNode head ) { ListNode prev = null ; ListNode curr = head ; while ( curr != null ) { ListNode nextTemp = curr . next ; curr . next = prev ; prev = curr ; curr = nextTemp ; } return prev ; } } class Solution_oj_recursively { public ListNode reverseList ( ListNode head ) { if ( head == null || head . next == null ) return head ; ListNode p = reverseList ( head . next ); head . next . next = head ; head . next = null ; return p ; } } class Solution_recursively { public ListNode reverseList ( ListNode head ) { ListNode dummy = new ListNode ( 0 ); // dummy.next = head; ListNode current = head ; reverse ( dummy , current ); return dummy . next ; } private void reverse ( ListNode dummy , ListNode current ) { if ( current == null ) { return ; } ListNode newHead = current . next ; ListNode oldDummyNext = dummy . next ; dummy . next = current ; current . next = oldDummyNext ; current = newHead ; this . reverse ( dummy , current ); } } class Solution_iteratively { public ListNode reverseList ( ListNode head ) { ListNode dummy = new ListNode ( 0 ); // dummy.next = head; ListNode current = head ; while ( current != null ) { ListNode newHead = current . next ; ListNode oldDummyNext = dummy . next ; dummy . next = current ; current . next = oldDummyNext ; // initial node, oldDummyNext is null, which is what we want, and which is why "// dummy.next = head;" is commented out above current = newHead ; } return dummy . next ; } } } ############ /** * 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; } * } */ class Solution { public ListNode reverseList ( ListNode head ) { ListNode dummy = new ListNode (); ListNode curr = head ; while ( curr != null ) { ListNode next = curr . next ; curr . next = dummy . next ; dummy . next = curr ; curr = next ; } return dummy . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList =
  function (head) {
    let dummy = new ListNode();
    let curr = head;
    while (curr) {
      let next = curr.next;
      curr.next = dummy.next;
      dummy.next = curr;
      curr = next;
    }
    return dummy.next;
  };

```

### Python

```python
# 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 ]: pre , p = None , head while p : q = p . next p . next = pre pre = p p = q return pre class Solution ( object ): # recursive def reverseList ( self , root ): if not root or not root . next : return root ret = self . reverseList ( root . next ) root . next . next = root # root.next is end of the newly reversed list ret root . next = None return ret class Solution : def reverseList ( self , head : ListNode ) -> ListNode : dummy = ListNode () curr = head while curr : next = curr . next curr . next = dummy . next dummy . next = curr curr = next return dummy . next
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/reverse-linked-list/ // Time: O(N) // Space: O(1) class Solution { public: ListNode * reverseList ( ListNode * head ) { ListNode h ; while ( head ) { auto p = head ; head = head -> next ; p -> next = h . next ; h . next = p ; } return h . next ; } };
```