LeetCode #206 Reverse Linked List

hey everyone👋

Today We discuss the leetcode #206 problem

Problem

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?

Solution — Iteration-

Use a pointer that points to a node x which is head at beginning. In each iteration if it has next node y ,move next node to be front of current head and update head pointer to y. Once x has not next node, i.e. it’s tail, end the iteration.


# Python3

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

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # Iteration approach
        # Run one pointer p in list. At each iteration:
        #     1. n = p.next
        #     2. p.next = n.next, jump cross n
        #     3. n.next = head, n prepend to the front
        #     4. head = n, reassign head

        if head == None:
            return None

        p = head
        while p.next:
            n = p.next
            p.next = n.next
            n.next = head
            head = n

        return head

Complexity-

the time complexity is O(n) if n denotes to counts of nodes in this linked list.

It’s trivial that it only uses O(1) extra space.

Solution — Recursion

# Python3

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

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        # Recursion approach:
        #     take head and reverse list whose head is head.next
        #     then reversely assign the link between them

        if head == None or head.next == None:
            return head

        n = head.next
        h = self.reverseList(n)

        # reverse link
        head.next = None
        n.next = head

        return h

Complexity

At each function call, it’s only takes** O(1) time for assigning link**. And there are n-2 calls if n denotes to counts of nodes in this linked list. Therefore, time complexity will be O(n).

Also, it **uses O(1) extra space **in each function call and there are n-2 calls in calling stack. Hence space complexity is O(n) as well.

Thank you for read this article .I hope its help you to solve this problem
If you like the article so just follow on *@coders_village in instagram *

Thank You
Shivani Tiwari
(Software Developers)

Blog