206_Reverse Linked List

Question

Reverse a singly linked list.

Example: we have linked list1 → 2 → 3 → Ø, we would like to change it toØ ← 1 ← 2 ← 3.

Solution 1: brute force (traverse twice)

convert the linked list to a array, and then convert the array to a new linked list in another direction.

    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """            
        if not head:
            return head

        # brute force
        # convert to array
        res = []
        pointer = head
        while pointer is not None:
            res.append(pointer.val)
            pointer = pointer.next
        # convert back to a new linked list
        ret = ListNode(res[0])
        for item in res[1:]:
            ret = self.helper(ret, item)
        return ret

    def helper(self, head, num):
        ret = ListNode(num)
        ret.next = head
        return ret

Idea: reverse linked list when traverse each element (traverse once)

While you are traversing the list, change the current node's next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference.

Time complexity : $O(n)$

Space complexity : $O(1)$

Solution 2: recursively

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

class Solution(object):    
    def reverseList(self, next_node, prev_node=None):
        if not next_node:
            return prev_node
        cur_node = next_node
        next_node = next_node.next
        cur_node.next = prev_node
        prev_node = cur_node
        return self.reverseList(next_node, prev_node)

Solution 3: iteratively

class Solution(object):
    def reverseList(self, next_node):
        """
        :type next_node: ListNode
        :rtype: ListNode
        """
        if not next_node:
            return next_node
        prev_node = None
        while next_node:
            cur_node = next_node
            next_node = next_node.next
            cur_node.next = prev_node
            prev_node = cur_node
        return prev_node

Follow up: what if the final node is linked to itself?

Solution: iteratively

class Solution(object):
    def reverseList(self, next_node):
        """
        :type next_node: ListNode
        :rtype: ListNode
        """
        if not next_node:
            return next_node
        prev_node = next_node.val
        while next_node:
            cur_node = next_node
            next_node = next_node.next
            cur_node.next = prev_node
            prev_node = cur_node
        return prev_node