DEV Community

loading...
Cover image for LinkedList Questions: Reverse a Linked List - Iterative version

LinkedList Questions: Reverse a Linked List - Iterative version

Kathan Vakharia
DS-Algo Tenderfoot | Computer Scientist | Aspiring Gopher | DataScience Enthusiast | Python & C++ ๐Ÿ’•
ใƒปUpdated on ใƒป2 min read

In this series of posts, I will discuss coding questions on the LinkedList Data structure.
The posts in this series will be organized in the following way,

  1. Question Link โ“
  2. Possible Explanation ๐Ÿ“
  3. Documented C++ Code ๐Ÿงน
  4. Time and Space Complexity Analysis โŒ›๐ŸŒŒ

The Question

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

https://leetcode.com/problems/reverse-linked-list/

๐Ÿ’ก Give yourself at least 15-20 mins to figure out the solution :)

๐Ÿ’๐Ÿปโ€โ™‚๏ธ Tip: You need to be good at pointer manipulations.

Explanation

We will go through every node and make it point to its preceding node. The idea is fairly simple, it's all about pointer manipulations and how you will do it. Here's the algorithm,

  • Initialize three pointers, prev = null, nex = null, cur = head. At every iteration cur will point to the current node, prev will point to its preceding node and nex will point to its succeeding node.
  • while cur โ‰  null i.e until we haven't reversed every node
    • nex = cur ( Before we change cur's next, take hold of its succeeding node )
    • cur โ†’ next = prev ( Reverse the link )
    • prev = cur (Update prev for following iteration )
    • cur = nex (Update cur for following iteration )
  • Make head = prev ( prev points to the first node of reversed linked list )
  • return head

Here's a dry run on a list of 5 elements to make things more clear,

Dry run of algorithm

C++ Code

Definition of LinkedList

//Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

Enter fullscreen mode Exit fullscreen mode

Solution

ListNode *reverseList(ListNode *head)
    {

        ListNode *prev = nullptr;
        ListNode *cur = head;
        ListNode *next = nullptr;

        //while cur is pointing to a node
        while (cur)
        {
            //get access to the node ahead
            next = cur->next;

            //break the forward link
            cur->next = prev;

            //moving prev ahead
            prev = cur;

            //updating current node
            cur = next;
        }
        //After the loop, prev will be pointed to the required node
        head = prev;
        return head;
    }
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Time Complexity: O(n)

We are traveling every node.

Space Complexity: O(1)

We didn't use any extra space.

๐Ÿ’ก Can you think of a recursive solution? I will answer this in the next post.

Discussion (0)