206. Reverse Linked List

LeetCode Problem Link (opens new window)

Problem Description: Reverse a singly linked list.

Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Approach

If a new linked list is defined to achieve the reversal, this actually wastes memory space.

In fact, you only need to change the direction of the next pointer of the linked list to reverse it directly, without re-defining a new linked list, as shown in the diagram:

The head node of the linked list was element 1, and after reversal, the head node is element 5. No nodes were added or deleted; only the directions of the next pointers were changed.

Now, let's see how the reversal is done:

Here's an example making use of a linked list from the problem example, as shown in the animation below: (Correction: The animation should show pre being moved before cur.)

First, define a cur pointer pointing to the head node, and then define a pre pointer initialized to null.

Next, the reversal begins by first saving the cur->next node using a tmp pointer. So why do we save this node? Because we're about to change the direction of cur->next, pointing it to pre. At this point, the first node has been reversed.

The steps need to be repeated in a loop, continuing to update the pre and cur pointers.

Finally, when the cur pointer points to null, the loop ends, and the linked list is fully reversed. At this point, return the pre pointer which points to the new head node.

Two-Pointer Method

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // Save next node of cur
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // Save next node of cur because the next of cur will be changed
            cur->next = pre; // Reversal operation
            // Update pointers pre and cur
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(1)

Recursive Method

The recursive method is relatively abstract, but in fact, it is the same logic as the two-pointer method, also ending the loop when cur is null and constantly making cur point to pre.

The key is the initialization part, which some might not understand. It can be seen that in the two-pointer method cur = head and pre = NULL, in the recursive method, the initialization logic is the same, just written differently.

The specific implementation is shown in the code with detailed comments. Once you write out the two-pointer method, it is not difficult to understand the following recursive method as the code logic is the same.

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // Compare with the code in two-pointer method. The following recursive writing actually does these two steps:
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // The initialization logic is the same as in two-pointer method
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }
};

• Time Complexity: O(n), since each node in the linked list is processed recursively
• Space Complexity: O(n), due to the recursive call stack with n levels

We notice that the recursive method above and the two-pointer method both reverse the pointers from front to back, but there is another recursive method that reverses the pointers from back to front.

The specific implementation is shown in the code with detailed comments:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // Edge case
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // Recursive call to reverse the list starting from the second node
        ListNode *last = reverseList(head->next);
        // Reverse the direction between the head node and the second node
        head->next->next = head;
        // The head node is now the tail node, so its next should be NULL
        head->next = NULL;
        return last;
    }
};

• Time Complexity: O(n)
• Space Complexity: O(n)

Other Language Versions

Java:

// Two-pointer
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// Save next node
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

// Recursive 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// Save next node first
        cur.next = prev;// Reverse
        // Update prev, cur position
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

// Recursive from back to front
class Solution {
    ListNode reverseList(ListNode head) {
        // Edge cases
        if(head == null) return null;
        if (head.next == null) return head;
        
        // Recursive call to reverse the list from the second node onward
        ListNode last = reverseList(head.next);
        // Reverse the direction between the head node and the second node
        head.next.next = head;
        // The head node is now a tail node, so its next should point to NULL
        head.next = null;
        return last;
    } 
}

Python:

# Two-pointer
# 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: ListNode) -> ListNode:
        cur = head   
        pre = None
        while cur:
            temp = cur.next # Save next node of cur since we're changing cur->next
            cur.next = pre # Reverse
            # Update pointers pre, cur
            pre = cur
            cur = temp
        return pre

# Recursive
# 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: ListNode) -> ListNode:
        return self.reverse(head, None)
    def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse(temp, cur)

Go:

// Two-pointer
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

// Recursive
func reverseList(head *ListNode) *ListNode {
    return help(nil, head)
}

func help(pre, head *ListNode)*ListNode{
    if head == nil {
        return pre
    }
    next := head.Next
    head.Next = pre
    return help(head, next)
}

JavaScript:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */

// Two-pointer:
var reverseList = function(head) {
    if(!head || !head.next) return head;
    let temp = null, pre = null, cur = head;
    while(cur) {
        temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    // temp = cur = null;
    return pre;
};

// Recursive:
var reverse = function(pre, head) {
    if(!head) return pre;
    const temp = head.next;
    head.next = pre;
    pre = head
    return reverse(pre, temp);
}

var reverseList = function(head) {
    return reverse(null, head);
};

// Recursive 2
var reverse = function(head) {
    if(!head || !head.next) return head;
    // Reverse from back to front
    const pre = reverse(head.next);
    head.next = pre.next;
    pre.next = head;
    return head;
}

var reverseList = function(head) {
    let cur = head;
    while(cur && cur.next) {
        cur = cur.next;
    }
    reverse(head);
    return cur;
};

TypeScript:

// Two-pointer method
function reverseList(head: ListNode | null): ListNode | null {
    let preNode: ListNode | null = null,
        curNode: ListNode | null = head,
        tempNode: ListNode | null;
    while (curNode) {
        tempNode = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
    }
    return preNode;
};

// Recursive (reverse from front to back)
function reverseList(head: ListNode | null): ListNode | null {
    function recur(preNode: ListNode | null, curNode: ListNode | null): ListNode | null {
        if (curNode === null) return preNode;
        let tempNode: ListNode | null = curNode.next;
        curNode.next = preNode;
        preNode = curNode;
        curNode = tempNode;
        return recur(preNode, curNode);
    }
    return recur(null, head);
};

// Recursive (reverse from back to front)
function reverseList(head: ListNode | null): ListNode | null {
    if (head === null) return null;
    let newHead: ListNode | null;
    function recur(node: ListNode | null, preNode: ListNode | null): void {
        if (node.next === null) {
            newHead = node;
            newHead.next = preNode;
        } else {
            recur(node.next, node);
            node.next = preNode;
        }
    }
    recur(head, null);
    return newHead;
};

Ruby:

# Two-pointer
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
def reverse_list(head)
  # return nil if head.nil? - the loop condition also ensures this so no need for separate check
  cur, per = head, nil
  until cur.nil?
    tem = cur.next
    cur.next = per
    per = cur
    cur = tem
  end
  per
end

# Recursive
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
def reverse_list(head)
  reverse(nil, head)
end

def reverse(pre, cur)
  return pre if cur.nil?
  tem = cur.next
  cur.next = pre
  reverse(cur, tem)	# This is equivalent to updating the pre and cur in the two-pointer method
end

Kotlin:

fun reverseList(head: ListNode?): ListNode? {
    var pre: ListNode? = null
    var cur = head
    while (cur != null) {
        val temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    return pre
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        // temp to store temporary node
        var temp: ListNode?
        // cur to traverse the linked list
        var cur: ListNode? = head
        // pre as a tool to reverse the linked list
        // pre is the node before the current node
        var pre: ListNode? = null
        while (cur != null) {
            // Temporarily store the next node of cur
            temp = cur.next
            // Make the next of cur point to the previous node
            cur.next = pre
            // Move pre along with cur as it traverses
            pre = cur;
            // Move cur to traverse the nodes in the linked list
            cur = temp;
        }
        // As pre was initialized with null, cur is now at null which is after the end of the list
        // So pre is now the head node
        return pre;
    }
}

Swift：

/// Two-pointer Method (Iterative)
/// - Parameter head: Head node
/// - Returns: Reversed linked list head node
func reverseList(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }
    var pre: ListNode? = nil
    var cur: ListNode? = head
    var temp: ListNode? = nil
    while cur != nil {
        temp = cur?.next
        cur?.next = pre
        pre = cur
        cur = temp
    }
    return pre
}

/// Recursive
/// - Parameter head: Head node
/// - Returns: The head node of the reversed linked list
func reverseList2(_ head: ListNode?) -> ListNode? {
    return reverse(pre: nil, cur: head)
}
func reverse(pre: ListNode?, cur: ListNode?) -> ListNode? {
    if cur == nil {
        return pre
    }
    let temp: ListNode? = cur?.next
    cur?.next = pre
    return reverse(pre: cur, cur: temp)
}

C:

Two-pointer method:

struct ListNode* reverseList(struct ListNode* head){
    //Save next node of cur
    struct ListNode* temp;
    //pre pointer points to the node before cur
    struct ListNode* pre = NULL;
    //head is used instead of cur, but you may define a cur node pointing to head.
    while(head) {
        //Save next node
        temp = head->next;
        //Reverse operation
        head->next = pre;
        //Update pointers
        pre = head;
        head = temp;
    }
    return pre;
}

Recursive method:

struct ListNode* reverse(struct ListNode* pre, struct ListNode* cur) {
    if(!cur)
        return pre;
    struct ListNode* temp = cur->next;
    cur->next = pre;
    //Pass cur as pre to next level
    //Pass temp as cur to next level to change the pointer to cur
    return reverse(cur, temp);
}

struct ListNode* reverseList(struct ListNode* head){
    return reverse(NULL, head);
}

PHP:

// Two-pointer method:
function reverseList($head) {
    $cur = $head;
    $pre = NULL;
    while($cur){
        $temp = $cur->next; 
        $cur->next = $pre;
        $pre = $cur;
        $cur = $temp;
    }
    return $pre;
}

Scala:

Two-pointer method:

object Solution {
  def reverseList(head: ListNode): ListNode = {
    var pre: ListNode = null
    var cur = head
    while (cur != null) {
      var tmp = cur.next
      cur.next = pre
      pre = cur
      cur = tmp
    }
    pre
  }
}

Recursive method:

object Solution {
  def reverseList(head: ListNode): ListNode = {
    reverse(null, head)
  }

  def reverse(pre: ListNode, cur: ListNode): ListNode = {
    if (cur == null) {
      return pre    // Return pre if cur is null
    }
    val tmp: ListNode = cur.next
    cur.next = pre
    reverse(cur, tmp)   // cur becomes the previous node, tmp becomes current node
  }
}

Rust:

Two-pointer method:

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut cur = head;
        let mut pre = None;
        while let Some(mut node) = cur.take() {
            cur = node.next;
            node.next = pre;
            pre = Some(node);
        }
        pre
    }
}

Recursive method:

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        fn rev(
            mut head: Option<Box<ListNode>>,
            mut pre: Option<Box<ListNode>>,
        ) -> Option<Box<ListNode>> {
            if let Some(mut node) = head.take() {
                let cur = node.next;
                node.next = pre;
                pre = Some(node);
                return rev(cur, pre);
            }
            pre
        }
        rev(head, None)
    }
}

C#:

Three-pointer method which might be more intuitive:

public LinkNumbers Reverse()
{
    // Using three pointers to make up for visualization issues in two-pointer method during reversal
    LinkNumbers pre = null;
    var move = root;
    var next = root;

    while (next != null)
    {
        next = next.linknext;
        move.linknext = pre;
        pre = move;
        move = next;
    }
    root = pre;
    return root;
}

/// LinkNumbers class definition
public class LinkNumbers
{
    /// <summary>
    /// Value of the linked list
    /// </summary>
    public int value { get; set; }

    /// <summary>
    /// Pointer in the linked list
    /// </summary>
    public LinkNumbers linknext { get; set; }
}

Other Solutions

Use a dummy head node to solve the linked list reversal

Use a dummy head node and achieve reversal by inserting nodes at the head (head insertion method).

// Iterative method: Add a dummy head node and reverse the linked list using head insertion method
public static ListNode reverseList1(ListNode head) {
    // Create a dummy head node
    ListNode dumpyHead = new ListNode(-1);
    dumpyHead.next = null;
    // Traverse all nodes
    ListNode cur = head;
    while(cur != null){
        ListNode temp = cur.next;
        // Head insertion
        cur.next = dumpyHead.next;
        dumpyHead.next = cur;
        cur = temp;
    }
    return dumpyHead.next;
}

Use stack to solve the problem of reversing a linked list

• First, push all nodes onto the stack.
• Then create a dummy head node and point cur to the dummy head node. After that, start popping from the stack, and for each element that comes out, add it to the list with the dummy head node as the head. Finally, return the list.

public ListNode reverseList(ListNode head) {
    // If the list is empty, return null
    if (head == null) return null;
    // If there's only one element in the linked list, return it directly
    if (head.next == null) return head;
    // Create a stack and push each node onto it
    Stack<ListNode> stack = new Stack<>();
    ListNode cur = head;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    // Create a dummy head node
    ListNode pHead = new ListNode(0);
    cur = pHead;
    while (!stack.isEmpty()) {
        ListNode node = stack.pop();
        cur.next = node;
        cur = cur.next;
    }
    // The next of the last node needs to be set to null
    cur.next = null;
    return pHead.next;
}

Using this method, note that after the entire stack popping loop ends, cur exactly points to the original first node in the linked list, and at this time, node 1's next points to node 2. Therefore, cur.next = null is needed at the end.