How to reverse a singly linked list - Data Structure And Algorithms - 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

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

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)

}

0 People on 20 March 2018

Existing User

New User