Teaching Kids Programming – Reverse a Linked List using Recursion and Iterative Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

Reverse a singly linked list.

Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

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

Iterative Algorithm to Reverse a Linked List

We keep updating the previous node and current node along the linked list, and reverse the link directions e.g. pointing the current node to previous node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        cur = head
        while cur:
            nextTemp = cur.next
            cur.next = prev
            prev = cur
            cur = nextTemp
        return prev

Time complexity is O(N), where need to visit N nodes in the linked list. And Space requirement is O(1).

Recursive Algorithm to Reverse a Linked List

We can reverse this in Recursion manner. We can reverse every other nodes except current node, then reverse the link direction.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        n = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return n

The Recursion can be tail optimised to O(N). The space complexity is O(N) where N is the number of the nodes in the linked list.

Reverse the LinkList by Changing the Node Value

If we are allowed to change the node values, we don’t need to modify the link directions. We can then go through the linked list twice. The first time we copy the node values to an array, the second time we assign the node values (in reversed order) to each node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        data = []
        p = head
        while p:
            data.append(p.val)
            p = p.next
        p = head
        while p:
            p.val = data.pop()
            p = p.next
        return head

Related Posts

• How to Reverse Linked List within Interval? (C/C++)
• How to Print Immutable Linked List in Reverse using Recursion or Stack?
• How to Reverse a Linked List in Javascript?
• How to Reverse a Linked List in C/C++?

–EOF (The Ultimate Computing & Technology Blog)