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
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