How to reverse LinkedList(Node) with O(n) Time and O(1) Space

Information

• Time complexity : O(n)
• Space complexity : O(1)
• input : head node of LinkedList
• output : head node of LinkedList

Java Code

public static ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Steps

1. ListNode prev = null;

2. ListNode next = head.next;

3. head.next = prev;

4. prev = head;

5. head = next;

6. while (head != null)

7. ListNode next = head.next;

8. head.next = prev;

9. prev = head;

10. head = next;

11. while (head != null)

12. ListNode next = head.next;

13. head.next = prev;

14. prev = head;

15. head = next;

16. while (head != null), return prev;