Leetcode: Reverse a Linked List

 This question was extremely common, being asked at Amazon, Adobe, Facebook, Apple, and Microsoft. It is as follows:

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

Here are the examples: 

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

The solution is simple.

Let there be 3 pointers. One will be current, then a previous node, then a next node.

We want to set the next pointer to equal the previous node, as well as make the previous the current, and the current = the nextTemp node. Here is the code: 

public ListNode reverseList(ListNode head) {

    //get the previous and current node

    ListNode prev = null;

    ListNode curr = head; 

    //iterate through the linked list

    while (curr != null) {

        ListNode nextTemp = curr.next; 

        //make the current node next equal to previous, then reverse it 

        curr.next = prev;

        //move the previous and current node up 1 iteration, and repeat the process. 

        prev = curr; 

        curr = nextTemp;

    }

    return prev; 

}

The next solution is the recursive solution. This solution is slightly trickier, and we want to assume that the rest of the list has been reversed. 

Let's assume that node nk+1 to nm have been reversed and you are at node nk.

The time complexity and the space complexity of this problem is O(n). 

We want nk+1's next node to point to nk, so we can figure out that nk.next.next = nk, and we nullify nk's next pointer since this will be solved in a previous iteration, otherwise your linked list would have a cycle in it. We want to get rid of this cycle.

The following is the final code (in Python): 

class Solution(object):

    def reverseList(self, head):

        """

        :type head: ListNode

        :rtype: ListNode

        """

        #figure out if the linked list is empty

        if not head or not head.next: 

            return head

        #recursively call the final list.

        p = self.reverseList(head.next)

        #reversing step 

        head.next.next = head

        #remove the cycle from the list

        head.next = None

        return p