Solutions

1. Two Pointers

O(n) time | O(1) space

Intuition

We can traverse through the list keeping a pointer to the previous node, and point each node to it at each iteration.

Algorithm

Create previous and current variables with current pointing to the head.
Traverse through the list while current is not empty.
- Point current back to previous.
- Move previous to current, and current to the next node.
Return previous.

∅previous → 1current → 2 → 3 → 4 → ∅

point 1 back to nothing

1 / 5

Code

# Definitions:
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def reverseList(head: ListNode) -> ListNode:
    previous = None
    current = head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    return previous

// Definitions:
// function ListNode(val, next) {
//     this.val = val === undefined ? 0 : val
//     this.next = next === undefined ? null : next
// }

/**
 * @param {ListNode} head
 * @returns {ListNode}
 */
var reverseList = function (head) {
  let previous = null
  let current = head
  while (current) {
    const nextNode = current.next
    current.next = previous
    previous = current
    current = nextNode
  }
  return previous
}

// Definitions:
// 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 previous = null;
        ListNode current = head;
        while (current != null) {
            ListNode nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
        }
        return previous;
    }
}