206 Reverse Linked List

Reverse a singly linked list.

The Idea: Reverse the next pointer of every node. Consider the following example:

input:
1 -> 2 -> 3 -> 4 -> 5 -> null

start: first set head->next to null, but remember to store next
null <- 1 ...

now enter the while loop: terminate when iter_next is null

null <- 1 <- 2 ...
null <- 1 <- 2 <- 3 ...
null <- 1 <- 2 <- 3 <- 4 ...
null <- 1 <- 2 <- 3 <- 4 <- 5

Complexity: O(n) time and O(1) space

# 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
        """
        if not head:
            return head

        iter_next = head.next
        head.next = None
        while iter_next:
            tmp = iter_next.next
            iter_next.next = head
            head = iter_next
            iter_next = tmp
        return head