How to reverse a singly linked list


Category: Data Structure And Algorithms Tags: C#, Java, C++ Programming, Interview Question

Suppose given singly linked list: Head -> 5- > 2 -> 3 -> 1 -> null I want to reverse it like: Head -> 1 -> 3- > 2 -> 5 -> null


Like 0 People
Asked on 10 April 2017
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 126
Questions: 9
Given Best Solutions: 8 *

Answers:

Nikhil Joshi

Given linked list is a singly list suppose Node structure is:

Node
{
   int Value { get; set; }
   Node Next { get; set; }
}

Now we write method to reverse linked list:

public void Reverse(Node head)
{
    Node pre = null;
    Node current = head;
    Node next = null;
    while (current != null)
    {
        next = current.Next;    //storing next pointer of current node
        current.Next = pre;      //making 2 -> 3 to 2 <- 3 (next pointer to previous node)
        pre = current;             //storing current pointer
        current = next;           //making current equals to next
    }
    Head = pre;                   //setting Head to last node in order to reverse
}

To reverse a singly list we needed three pointers pre, current and next. First we start from head and copy head reference (value = 5 in our scenario) in current, Next node(2 in our scenario) we copy in next pointer, now we have to reverse where we have to make current pointer's next pointer to previous node, because 5 is head so we have to make its next pointer null in order to reverse(but for 2->3 we make it 2<-3 in next iteration) so we set current.Next pointer to pre. again we copy current node pointer in pre for next iteration. And in last line of loop we set current as next so now current is node which value=2 and so on. Let's see it how it works, suppose we have AddNode and Traverse methods to add nodes and print nodes, we can see output by running code:

SinglyList linkedList = new SinglyList();
linkedList.AddNode(new Node(5));
linkedList.AddNode(new Node(2));
linkedList.AddNode(new Node(3));
linkedList.AddNode(new Node(1));
Console.WriteLine("Sequence of nodes:");
linkedList.Traverse(linkedList.Head); //traversing
linkedList.Reverse(linkedList.Head); //reversing
Console.WriteLine("Sequence of nodes after reversing:");
linkedList.Traverse(linkedList.Head);

Output: Sequence of nodes: 5 2 3 1 Sequence of nodes after reversing: 1 3 2 5
To learn linked lists in detail refer link: https://www.dotnetlovers.com/Article/145/implementation-and-analysis-of-linked-list-data-structure

Like 0 People on 10 April 2017
Bibek Behera
using System;
using System.Collections.Generic;
//Bibek Kumar Behera
public class singleLinkedList
{
    public class Node
    {
        public int data;
        public Node Next;
    }
}
 
 
public void reverse(Node prev, Node curr, ref Node head)
{
    if (curr == null)
    {
        head = prev;
        return;
    }
    reverse(prev.Next, curr.Next, ref head);
    prev.Next.Next = prev;
    prev.Next = null;
}
 
//Driver programe
 
class Program
{
    static void Main(string[] args)
    {
        List First = new List();
        
        First.Add(1);
        First.Add(2);
        First.Add(3);
        First.Add(4);
        First.Add(5);
        First.Add(6);
        First.Add(7);
        First.Add(8);
        First.Add(9);
 
        List.Node testNode = new List.Node();
        First.reverse(First.head, First.head.Next, ref testNode);
 
        //Here testNode will become 9->8->7->6->5->4->3->3->2->1
        //Time Complexity: O(n)
        //Space Complexity: O(1)
 
    }
}
Like 0 People on 20 March 2018
mehrab alam

algorithum linked list 

Like 0 People on 19 November 2018

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x