Skip to main content

Fold linked list in c#

Csharp program for Fold linked list. Here problem description and other solutions.

// Include namespace system
using System;
/*
  Csharp program for
  Fold linked list
*/
// 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 SingleLL()
	{
		// Set initial value
		this.head = null;
	}
	// Add node at the beginning
	public void addNode(int data)
	{
		// Create new node
		var node = new LinkNode(data);
		node.next = this.head;
		// Set new head
		this.head = node;
	}
	// Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			return;
		}
		var temp = this.head;
		// iterating linked list elements
		while (temp != null)
		{
			Console.Write(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		Console.WriteLine(" NULL");
	}
	// This is handle the request of 
	// folding given linked list nodes
	public void foldList()
	{
		if (this.head == null)
		{
			Console.Write("\n Empty linked list");
			return;
		}
		// Some auxiliary variables
		var temp = this.head;
		var auxiliary = this.head;
		LinkNode hold = null;
		// Loops used to find the middle node
		while (temp != null && 
               temp.next != null && 
               temp.next.next != null)
		{
			// Visit to next node
			auxiliary = auxiliary.next;
			// Visit to second next node
			temp = temp.next.next;
		}
		if (auxiliary != null)
		{
			hold = auxiliary;
			auxiliary = auxiliary.next;
			// Separating half nodes
			hold.next = null;
			// Start with first node of next half section
			temp = auxiliary;
			auxiliary = null;
			// Reverse second half nodes 
			while (temp != null)
			{
				hold = temp;
				temp = temp.next;
				hold.next = auxiliary;
				auxiliary = hold;
			}
			// Start with first node of linked list
			temp = this.head;
			// Combine first and second half nodes 
			// in alternate manner
			while (temp != null)
			{
				hold = temp;
				temp = temp.next;
				hold.next = auxiliary;
				if (auxiliary != null)
				{
					hold = auxiliary;
					auxiliary = auxiliary.next;
					hold.next = temp;
				}
			}
		}
	}
	public static void Main(String[] args)
	{
		// Create a empty linked lists
		var sll1 = new SingleLL();
		var sll2 = new SingleLL();
		//  Constructed first linked list
		//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
		sll1.addNode(8);
		sll1.addNode(7);
		sll1.addNode(6);
		sll1.addNode(5);
		sll1.addNode(4);
		sll1.addNode(3);
		sll1.addNode(2);
		sll1.addNode(1);
		// Constructed second linked list
		//  1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
		sll2.addNode(7);
		sll2.addNode(6);
		sll2.addNode(5);
		sll2.addNode(4);
		sll2.addNode(3);
		sll2.addNode(2);
		sll2.addNode(1);
		// Test A
		Console.WriteLine(" Before folding");
		sll1.display();
		// Form of folding
		//      1 → 2 → 3 → 4 ──┐
		// NULL ← 8 ← 7 ← 6 ← 5⤶
		sll1.foldList();
		// After merging
		// 1 → 8 → 2 → 7 → 3 → 6 → 4 → 5 → NULL
		Console.WriteLine(" After folding");
		sll1.display();
		// Test B
		Console.WriteLine(" Before folding");
		sll2.display();
		// Form of folding
		//      1 → 2 → 3 → 4 
		// NULL ← 7 ← 6 ← 5⤶
		sll2.foldList();
		// After merging
		// 1 → 7 → 2 → 6 → 3 → 5 → 4 → NULL
		Console.WriteLine(" After folding");
		sll2.display();
	}
}

Output

 Before folding
 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
 After folding
 1 → 8 → 2 → 7 → 3 → 6 → 4 → 5 → NULL
 Before folding
 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
 After folding
 1 → 7 → 2 → 6 → 3 → 5 → 4 → NULL




Comment

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