Print reverse of a linked list without actually reversing

That is a linked list traversal problem, Displaying the linked list node in reverse order without effect (modified) in original linked list. Lets see few example.

Example A
Input List : 1 → 2 → 8 → 4 → 9 → 6 → NULL
Output     : 6   9   4   8   2   1
Example B
Input List : 1 → 2 → 3 → NULL
Output     : 3   2   1

This problem are targeted to understand iterative and recursive mechanism in programming language. Because recursion is simplest solution of this problem. And iterative is based on stack data structure. This post are based on recursive solution.

/*
    C program for
    Print reverse of a linked list without actually reversing
*/
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
	int data;
	struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
	struct LinkNode *head;
	struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
	// Create memory of head and tail Nodes
	struct SingleLL *sll = 
      (struct SingleLL *) malloc(sizeof(struct SingleLL));
	if (sll == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		sll->head = NULL;
		sll->tail = NULL;
	}
	return sll;
}
// Add new Node at end of linked list 
void appendNode(struct SingleLL *sll, struct LinkNode *node)
{
	if (sll->head == NULL)
	{
		sll->head = node;
	}
	else
	{
		// Append the node at last position
		sll->tail->next = node;
	}
	sll->tail = node;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
	// Create dynamic node
	struct LinkNode *node = 
      (struct LinkNode *) malloc(sizeof(struct LinkNode));
	if (node == NULL)
	{
		printf("Memory overflow to Create LinkNode\n");
		return;
	}
	else
	{
		// Set initial node value
		node->data = data;
		node->next = NULL;
	}
	appendNode(sll, node);
}
// Display Reversal view of linked list using recursion
void printReverse(struct LinkNode *node)
{
	if (node == NULL)
	{
		return;
	}
	// Visit to next node
	printReverse(node->next);
	// Display node value
	printf("  %d", node->data);
}
int main()
{
	struct SingleLL *sll = newLinkedList();
	//  1 → 2 → 8 → 4 → 9 → 6 → NULL
	addNode(sll, 1);
	addNode(sll, 2);
	addNode(sll, 8);
	addNode(sll, 4);
	addNode(sll, 9);
	addNode(sll, 6);
	// Reversal view
	// 6 9 4 8 2 1
	printReverse(sll->head);
	return 0;
}

Output

  6  9  4  8  2  1
// Java Program 
// Print reverse of a linked list without actually reversing

// Linked list node
class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public LinkNode tail;
	public SingleLL()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	public void addNode(int data)
	{
		LinkNode node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display Reversal view of linked list using recursion
	public void printReverse(LinkNode node)
	{
		if (node == null)
		{
			return;
		}
		// Visit to next node
		this.printReverse(node.next);
		// Display node value
		System.out.print(" " + node.data);
	}
	public static void main(String[] args)
	{
		SingleLL sll = new SingleLL();
		//  1 → 2 → 8 → 4 → 9 → 6 → NULL
		sll.addNode(1);
		sll.addNode(2);
		sll.addNode(8);
		sll.addNode(4);
		sll.addNode(9);
		sll.addNode(6);
		// Reversal view
		// 6 9 4 8 2 1
		sll.printReverse(sll.head);
	}
}

Output

 6 9 4 8 2 1
// Include header file
#include <iostream>
using namespace std;
// C++ Program 
// Print reverse of a linked list without actually reversing

// Linked list node
class LinkNode
{
	public: 
    int data;
	LinkNode *next;
	LinkNode(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};
class SingleLL
{
	public: 
    LinkNode *head;
	LinkNode *tail;
	SingleLL()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	// Add new Node at end of linked list 
	void addNode(int data)
	{
		LinkNode *node = new LinkNode(data);
		if (this->head == NULL)
		{
			this->head = node;
		}
		else
		{
			// Append the node at last position
			this->tail->next = node;
		}
		this->tail = node;
	}
	// Display Reversal view of linked list using recursion
	void printReverse(LinkNode *node)
	{
		if (node == NULL)
		{
			return;
		}
		// Visit to next node
		this->printReverse(node->next);
		// Display node value
		cout << " " << node->data;
	}
};
int main()
{
	SingleLL *sll = new SingleLL();
	//  1 → 2 → 8 → 4 → 9 → 6 → NULL
	sll->addNode(1);
	sll->addNode(2);
	sll->addNode(8);
	sll->addNode(4);
	sll->addNode(9);
	sll->addNode(6);
	// Reversal view
	// 6 9 4 8 2 1
	sll->printReverse(sll->head);
	return 0;
}

Output

 6 9 4 8 2 1
// Include namespace system
using System;
// Csharp Program 
// Print reverse of a linked list without actually reversing

// Linked list node
public class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode(int data)
	{
		this.data = data;
		this.next = null;
	}
}
public class SingleLL
{
	public LinkNode head;
	public LinkNode tail;
	public SingleLL()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	public void addNode(int data)
	{
		LinkNode node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display Reversal view of linked list using recursion
	public void printReverse(LinkNode node)
	{
		if (node == null)
		{
			return;
		}
		// Visit to next node
		this.printReverse(node.next);
		// Display node value
		Console.Write(" " + node.data);
	}
	public static void Main(String[] args)
	{
		SingleLL sll = new SingleLL();
		//  1 → 2 → 8 → 4 → 9 → 6 → NULL
		sll.addNode(1);
		sll.addNode(2);
		sll.addNode(8);
		sll.addNode(4);
		sll.addNode(9);
		sll.addNode(6);
		// Reversal view
		// 6 9 4 8 2 1
		sll.printReverse(sll.head);
	}
}

Output

 6 9 4 8 2 1
package main
import "fmt"
// Go Program 
// Print reverse of a linked list without actually reversing

// Linked list node
type LinkNode struct {
	data int
	next * LinkNode
}
func getLinkNode(data int) * LinkNode {
	var me *LinkNode = &LinkNode {}
	me.data = data
	me.next = nil
	return me
}
type SingleLL struct {
	head * LinkNode
	tail * LinkNode
}
func getSingleLL() * SingleLL {
	var me *SingleLL = &SingleLL {}
	me.head = nil
	me.tail = nil
	return me
}
// Add new Node at end of linked list 
func(this *SingleLL) addNode(data int) {
	var node * LinkNode = getLinkNode(data)
	if this.head == nil {
		this.head = node
	} else {
		// Append the node at last position
		this.tail.next = node
	}
	this.tail = node
}
// Display Reversal view of linked list using recursion
func(this SingleLL) printReverse(node * LinkNode) {
	if node == nil {
		return
	}
	// Visit to next node
	this.printReverse(node.next)
	// Display node value
	fmt.Print(" ", node.data)
}
func main() {
	var sll * SingleLL = getSingleLL()
	//  1 → 2 → 8 → 4 → 9 → 6 → NULL
	sll.addNode(1)
	sll.addNode(2)
	sll.addNode(8)
	sll.addNode(4)
	sll.addNode(9)
	sll.addNode(6)
	// Reversal view
	// 6 9 4 8 2 1
	sll.printReverse(sll.head)
}

Output

 6 9 4 8 2 1
<?php
// Php Program 
// Print reverse of a linked list without actually reversing

// Linked list node
class LinkNode
{
	public $data;
	public $next;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
	}
}
class SingleLL
{
	public $head;
	public $tail;
	public	function __construct()
	{
		$this->head = NULL;
		$this->tail = NULL;
	}
	// Add new Node at end of linked list 
	public	function addNode($data)
	{
		$node = new LinkNode($data);
		if ($this->head == NULL)
		{
			$this->head = $node;
		}
		else
		{
			// Append the node at last position
			$this->tail->next = $node;
		}
		$this->tail = $node;
	}
	// Display Reversal view of linked list using recursion
	public	function printReverse($node)
	{
		if ($node == NULL)
		{
			return;
		}
		// Visit to next node
		$this->printReverse($node->next);
		// Display node value
		echo(" ".$node->data);
	}
}

function main()
{
	$sll = new SingleLL();
	//  1 → 2 → 8 → 4 → 9 → 6 → NULL
	$sll->addNode(1);
	$sll->addNode(2);
	$sll->addNode(8);
	$sll->addNode(4);
	$sll->addNode(9);
	$sll->addNode(6);
	// Reversal view
	// 6 9 4 8 2 1
	$sll->printReverse($sll->head);
}
main();

Output

 6 9 4 8 2 1
// Node JS Program 
// Print reverse of a linked list without actually reversing

// Linked list node
class LinkNode
{
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	addNode(data)
	{
		var node = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display Reversal view of linked list using recursion
	printReverse(node)
	{
		if (node == null)
		{
			return;
		}
		// Visit to next node
		this.printReverse(node.next);
		// Display node value
		process.stdout.write(" " + node.data);
	}
}

function main()
{
	var sll = new SingleLL();
	//  1 → 2 → 8 → 4 → 9 → 6 → NULL
	sll.addNode(1);
	sll.addNode(2);
	sll.addNode(8);
	sll.addNode(4);
	sll.addNode(9);
	sll.addNode(6);
	// Reversal view
	// 6 9 4 8 2 1
	sll.printReverse(sll.head);
}
main();

Output

 6 9 4 8 2 1
#  Python 3 Program 
#  Print reverse of a linked list without actually reversing

#  Linked list node
class LinkNode :
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class SingleLL :
	def __init__(self) :
		self.head = None
		self.tail = None
	
	#  Add new Node at end of linked list 
	def addNode(self, data) :
		node = LinkNode(data)
		if (self.head == None) :
			self.head = node
		else :
			#  Append the node at last position
			self.tail.next = node
		
		self.tail = node
	
	#  Display Reversal view of linked list using recursion
	def printReverse(self, node) :
		if (node == None) :
			return
		
		#  Visit to next node
		self.printReverse(node.next)
		#  Display node value
		print(" ", node.data, end = "")
	

def main() :
	sll = SingleLL()
	#   1 → 2 → 8 → 4 → 9 → 6 → NULL
	sll.addNode(1)
	sll.addNode(2)
	sll.addNode(8)
	sll.addNode(4)
	sll.addNode(9)
	sll.addNode(6)
	#  Reversal view
	#  6 9 4 8 2 1
	sll.printReverse(sll.head)

if __name__ == "__main__": main()

Output

  6  9  4  8  2  1
#  Ruby Program 
#  Print reverse of a linked list without actually reversing

#  Linked list node
class LinkNode 
	# Define the accessor and reader of class LinkNode
	attr_reader :data, :next
	attr_accessor :data, :next
	def initialize(data) 
		self.data = data
		self.next = nil
	end

end

class SingleLL 
	# Define the accessor and reader of class SingleLL
	attr_reader :head, :tail
	attr_accessor :head, :tail
	def initialize() 
		self.head = nil
		self.tail = nil
	end

	#  Add new Node at end of linked list 
	def addNode(data) 
		node = LinkNode.new(data)
		if (self.head == nil) 
			self.head = node
		else
 
			#  Append the node at last position
			self.tail.next = node
		end

		self.tail = node
	end

	#  Display Reversal view of linked list using recursion
	def printReverse(node) 
		if (node == nil) 
			return
		end

		#  Visit to next node
		self.printReverse(node.next)
		#  Display node value
		print(" ", node.data)
	end

end

def main() 
	sll = SingleLL.new()
	#   1 → 2 → 8 → 4 → 9 → 6 → NULL
	sll.addNode(1)
	sll.addNode(2)
	sll.addNode(8)
	sll.addNode(4)
	sll.addNode(9)
	sll.addNode(6)
	#  Reversal view
	#  6 9 4 8 2 1
	sll.printReverse(sll.head)
end

main()

Output

 6 9 4 8 2 1
// Scala Program 
// Print reverse of a linked list without actually reversing

// Linked list node
class LinkNode(
  	var data: Int,
	var next: LinkNode)
{
	def this(data: Int)
	{
		this(data,null);
	}
}
class SingleLL(
  	var head: LinkNode,
	var tail: LinkNode)
{
	def this()
	{
		this(null,null);
	}
	// Add new Node at end of linked list 
	def addNode(data: Int): Unit = {
		var node: LinkNode = new LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display Reversal view of linked list using recursion
	def printReverse(node: LinkNode): Unit = {
		if (node == null)
		{
			return;
		}
		// Visit to next node
		this.printReverse(node.next);
		// Display node value
		print(" " + node.data);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var sll: SingleLL = new SingleLL();
		//  1 → 2 → 8 → 4 → 9 → 6 → NULL
		sll.addNode(1);
		sll.addNode(2);
		sll.addNode(8);
		sll.addNode(4);
		sll.addNode(9);
		sll.addNode(6);
		// Reversal view
		// 6 9 4 8 2 1
		sll.printReverse(sll.head);
	}
}

Output

 6 9 4 8 2 1
// Swift 4 Program 
// Print reverse of a linked list without actually reversing

// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class SingleLL
{
	var head: LinkNode? ;
	var tail: LinkNode? ;
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	// Add new Node at end of linked list 
	func addNode(_ data: Int)
	{
		let node: LinkNode = LinkNode(data);
		if (self.head == nil)
		{
			self.head = node;
		}
		else
		{
			// Append the node at last position
			self.tail!.next = node;
		}
		self.tail = node;
	}
	// Display Reversal view of linked list using recursion
	func printReverse(_ node: LinkNode? )
	{
		if (node == nil)
		{
			return;
		}
		// Visit to next node
		self.printReverse(node!.next);
		// Display node value
		print(" ", node!.data, terminator: "");
	}
}
func main()
{
	let sll: SingleLL = SingleLL();
	//  1 → 2 → 8 → 4 → 9 → 6 → NULL
	sll.addNode(1);
	sll.addNode(2);
	sll.addNode(8);
	sll.addNode(4);
	sll.addNode(9);
	sll.addNode(6);
	// Reversal view
	// 6 9 4 8 2 1
	sll.printReverse(sll.head);
}
main();

Output

  6  9  4  8  2  1
// Kotlin Program 
// Print reverse of a linked list without actually reversing

// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	var head: LinkNode ? ;
	var tail: LinkNode ? ;
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	// Add new Node at end of linked list 
	fun addNode(data: Int): Unit
	{
		val node: LinkNode = LinkNode(data);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			// Append the node at last position
			this.tail?.next = node;
		}
		this.tail = node;
	}
	// Display Reversal view of linked list using recursion
	fun printReverse(node: LinkNode ? ): Unit
	{
		if (node == null)
		{
			return;
		}
		// Visit to next node
		this.printReverse(node.next);
		// Display node value
		print(" " + node.data);
	}
}
fun main(args: Array < String > ): Unit
{
	val sll: SingleLL = SingleLL();
	//  1 → 2 → 8 → 4 → 9 → 6 → NULL
	sll.addNode(1);
	sll.addNode(2);
	sll.addNode(8);
	sll.addNode(4);
	sll.addNode(9);
	sll.addNode(6);
	// Reversal view
	// 6 9 4 8 2 1
	sll.printReverse(sll.head);
}

Output

 6 9 4 8 2 1


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved