Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution

/**
 * 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) {
        if (head == null || head.next == null)
        {
            return head;
        }
        ListNode current = head.next;
        ListNode prev = head;
        prev.next = null; // Make the original head the last node in the reversed list

        while (current != null)
        {
            ListNode nextTemp = current.next; // Temporarily store the next node
            current.next = prev; // Reverse the link
            prev = current; // Move prev one step forward
            current = nextTemp; // Move current one step forward
        }
        return prev; // Return the new head of the reversed list
    }
}

The time complexity of the algorithm is O(n), where n is the number of nodes in the linked list. This is because each node in the list is visited exactly once during the reversal process.

The space complexity of the algorithm is O(1). This is because the amount of extra space used does not grow with the size of the input linked list, and is therefore constant. The algorithm only uses a fixed amount of space to store pointers (i.e., current, prev, and nextTemp), regardless of the list size.