Reverse Linked List

• LeetCode: Reverse Linked List

• Problem:

Reverse a singly linked list.

• Hint:

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

• Analysis:

Original LinkedList: 1 -> 2 -> 3 -> NULL

Reversed LinkedList: 3 -> 2 -> 1 -> NULL

Reversed a node:

        -------    -------                                               -------    -------          
  Undo: |  A  | -> |  B  | -> ...                           Reversed:    |  Z  | -> |  Y  | -> NULL
        -------    -------                                               -------    -------
          / \        / \                                                   / \        
           |          |                                                     |         
          head    head.next                                                ptr

         -------    -------                                              -------     -------
  Undo:  |  A  |    |  B  | -> ...                          Reversed:    |  Z  |  -> |  Y  | -> NULL
         -------    -------                                              -------     -------
           / \        / \                                                  / \
            |          |                                                    |
           ptr         next                                                temp

         -------                                              -------    -------    -------
  Undo:  |  B  | -> ...                            Reversed:  |  A  | -> |  Z  | -> |  Y  | -> NULL
         -------                                              -------    -------    -------
           / \                                                  / \        
            |                                                    | 
           head                                                 ptr

• Code - Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode ptr = null;
        while (head != null) {
            ListNode next = head.next;
            ListNode rear = ptr;
            ptr = head;
            ptr.next = rear;
            head = next;
        }
        return ptr;
    }
}

• Code - C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* ptr = NULL;
        while (head != NULL) {
            ListNode* next = head->next;
            ListNode* rear = ptr;
            ptr = head;
            ptr->next = rear;
            head = next;
        }
        return ptr;
    }
};

• Code - Python:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        ptr = None
        while head != None:
            hNext = head.next;
            rear = ptr
            ptr = head
            ptr.next = rear
            head = Hnext
        return ptr

• Code - C:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* ptr = 0;
    while (head != 0) {
        struct ListNode* next = head->next;
        struct ListNode* rear = ptr;
        ptr = head;
        ptr->next = rear;
        head = next;
    }
    return ptr;
}

• Time Complexity: O(N), N is the length of singly-linked list

• Space Complexity: O(1)