## Archive for the ‘ LinkList ’ Category

Given a single linked list, we have to detect loop. For this we will use two pointers called slow and fast. We will increment slow by one and fast by two. once both these pointers meet, this is the node from were loop is present

```        public void DetectLoop(Node<T> node)
{
Node<T> slow = node;
Node<T> fast = node;

while (slow != fast && fast.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
if (slow == fast)
{
Console.WriteLine("Loop is detected");
return;
}
}
Console.WriteLine("There is no loop");

}```

Today we have to write a program for reversing a Doubly linked list. A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

Code

```        public DoubleNode<T> Reverse()
{
{
}
}```

Input : 0->1->2->3->4->5->6->7->8->9->

output: 1->0->3->2->5->4->7->6->9->8->

Code :

```        public void SwapEverySecondElement()
{
var q = p.Next;

while (q != null)
{
var temp = p.Data;
p.Data = q.Data;
q.Data = temp;
p = q.Next;
if (p != null)
{
q = p.Next;

}
else
{
q = null;
}

}

}```

Test

Input

0->1->2->3->4->5->6->7->8->9->

Output

1->0->3->2->5->4->7->6->9->8->

——————————————————————————–

Input

A->B->C->D->E->F->G->H->I->J->K->L->M->N->O->P->Q->R->S->T->U->V->W->X->Y->Z->

Output

B->A->D->C->F->E->H->G->J->I->L->K->N->M->P->O->R->Q->T->S->V->U->X->W->Z->Y->

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes’ previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

Code

```    public class DoubleLinkList<T>
{
private DoubleNode<T> tail;

{

{
item.Next = item.Previous = null;
tail = item;
return 0;
}

return 0;
}

public int InsertAtTail(DoubleNode<T> item)
{
{
item.Next = item.Previous = null;
tail = item;
return 0;
}

tail.Next = item;
item.Previous = tail;
tail = item;
return 0;
}

{
while (temp != null)
{
Console.Write(temp.Data + "->");
temp = temp.Next;
}
Console.WriteLine(Environment.NewLine);
}

{
var temp = root;
while (temp != null)
{
Console.Write(temp.Data + "->");
temp = temp.Next;
}
Console.WriteLine(Environment.NewLine);
}

public void ShowFromTail()
{
var temp = tail;
while (temp != null)
{
Console.Write(temp.Data + "->");
temp = temp.Previous;
}
Console.WriteLine(Environment.NewLine);
}
}

public class DoubleNode<T>
{
public DoubleNode<T> Next { get; set; }
public DoubleNode<T> Previous { get; set; }
public T Data { get; set; }

}```

Today we will write a program for appending last N nodes from the beginning to the start of the link list.

Example

input linked is 0->1->2->3->4->5->6->7->8->9 and the value of N is 3 than output must be

7->8->9->0->1->2->3->4->5->6

Code

```        public void AppendLastNNodeToHead(Node<T> root, int n)
{
Node<T> currentNode = root;
Node<T> previousNode = root;

for (int i = 0; i < n; i++)
{
currentNode = currentNode.Next;
if (currentNode == null)
{
Console.WriteLine("List has less number of nodes");
return;
}
}

while (currentNode.Next != null)
{
currentNode = currentNode.Next;
previousNode = previousNode.Next;
}

currentNode.Next = root;
root = previousNode.Next;
previousNode.Next = null;

}```

Today we will write a program for finding the Kth  element from the last.

Code

```        public void PrintKthElementFromLast(Node<T> head, int k)
{
int counter = 0;
while (counter < k)
{
if (firstPointer == null)
{
Console.WriteLine("LinkList has less number of nodes");
return;
}
firstPointer = firstPointer.Next;
counter = counter + 1;
}
while (firstPointer != null)
{
secondPointer = secondPointer.Next;
firstPointer = firstPointer.Next;
}
Console.WriteLine(string.Format("{0}th Elements from Last is {1} ", k,                                                             secondPointer.Data));
Console.WriteLine(Environment.NewLine);
}```

Test Case

1->2->3->4->5->6->

2th Elements from Last is 5

1->2->3->4->5->6->20->17->1->7->

3th Elements from Last is 17

1->2->3->4->5->6->20->17->1->7->

4th Elements from Last is 20

1->2->3->4->5->6->20->17->1->7->

10th Elements from Last is 1

In the past we have already covered reversing a Linked List via Recursion.  Today we will discuss how we can reverse a Linked List using Iterative method.

# Algorithm

1. Take three pointer currentNode,nextNode and previousNode
3. iterate over the linked list until currentNode is equal to null
1. nextNode to previousNode
2. previousNode to currentNode
3. In the loop change currentNode to next Node
4. return previousNode

Code

```        public Node<T> ReverseIterative()
{

Node<T> previousNode, nextNode;
previousNode = nextNode = null;

while (currentNode != null)
{
nextNode = currentNode.Next;
currentNode.Next = previousNode;
previousNode = currentNode;
currentNode = nextNode;

}
return previousNode;
}```

# Algorithm

1. Initialize number counter to 0
2. Loop through the linked list
1. if current node value is equal to number, increment the counter
3. return counter

Code

```        public int NumberCount(T number)
{
int count = 0;

while (temp != null)
{
if (temp.Data.Equals(number))
{
count = count + 1;
}
temp = temp.Next;
}
return count;
}```

sub list of a sorted (ascending order)link list is reversed. correct it.

Input
1->2->3->4->8->7->6->5->9->10->11
Output
1->2->3->4->5->6->7->8->9->10->11

To solve this problem :

1. Find the pointer, from dis order starts say first
2. Find the pointer where dis order ends say last node
3. Setting next of last node to null
4. Reverse the linked list from first to last
6. join the linked list with remaining list

Node Class : Used for Creating Link List

```public class Node<T>
{
private T nodeValue;
private Node<T> nextNode;

public Node()
{
this.nodeValue = default(T);
this.nextNode = null;
}

public Node(T nodeValue)
{
this.nodeValue = nodeValue;
this.nextNode = null;
}

/// <summary>
/// Value of node
/// </summary>
public T NodeValue
{
get { return nodeValue; }
set { this.nodeValue = value; }
}

/// <summary>
/// The node this node links to
/// </summary>
public Node<T> NextNode
{
get { return this.nextNode; }
set { this.nextNode = value; }
}
}```
```    /// <summary>
/// 1--->2--->3--->4--->9--->8-->7--->6--->5--->10--->11--->NULL
/// </summary>
{

{
Console.WriteLine("Empty List");
return;
}

Node<int> first = null;
Node<int> last = null;
Node<int> mark1 = null;

while (current != null && current.NodeValue < current.NextNode.NodeValue)
{
mark1 = current;
current = current.NextNode;
}

first = current; //Pointer to node, LL Disorder starts

while (current != null && current.NodeValue > current.NextNode.NodeValue)
current = current.NextNode;

last = current.NextNode; //Pointer to node, LL Disorder Ends

current.NextNode = null; // Setting next of last node to null

Reverse(ref first);//reverse the sub list that dis order starts to disorder ends

while (first.NextNode != null)
{
first = first.NextNode;
}

first.NextNode = last; // join the merged link list with sorted linklist
Console.WriteLine();
Console.WriteLine("Output");

Console.WriteLine();

}

public static void Reverse(ref Node<int> head)
{

Node<int> first;
Node<int> rest;
rest = first.NextNode;
if (rest == null) return;
Reverse(ref rest);
first.NextNode.NextNode = first;
first.NextNode = null;

}
{
{
}

}```

## Main Program

```      Node<int> a = new Node<int>(1);
Node<int> a1 = new Node<int>(2);
Node<int> a2 = new Node<int>(3);
Node<int> a3 = new Node<int>(4);
Node<int> a4 = new Node<int>(8);
Node<int> a5 = new Node<int>(7);
Node<int> a6 = new Node<int>(6);
Node<int> a7 = new Node<int>(5);
Node<int> a8 = new Node<int>(9);
Node<int> a9 = new Node<int>(10);
Node<int> a10 = new Node<int>(11);

a.NextNode = a1;
a1.NextNode = a2;

a2.NextNode = a3;

a3.NextNode = a4;

a4.NextNode = a5;

a5.NextNode = a6;

a6.NextNode = a7;

a7.NextNode = a8;

a8.NextNode = a9;

a9.NextNode = a10;

a10.NextNode = null;
Console.WriteLine("Input");
Microsoft.PrintList(a);
Microsoft.correctList(a);```

Node Class : For creating LinkList

```public class Node<T>
{
private T nodeValue;
private Node<T> nextNode;

public Node()
{
this.nodeValue = default(T);
this.nextNode = null;
}

public Node(T nodeValue)
{
this.nodeValue = nodeValue;
this.nextNode = null;
}

/// <summary>
/// Value of node
/// </summary>
public T NodeValue
{
get { return nodeValue; }
set { this.nodeValue = value; }
}

/// <summary>
/// The node this node links to
/// </summary>
public Node<T> NextNode
{
get { return this.nextNode; }
set { this.nextNode = value; }
}
}```

```class LinkList
{
public static void Test()
{
Node<int> a1 = new Node<int>();
a1.NodeValue = 10;

Node<int> a2 = new Node<int>();
a2.NodeValue = 11;

Node<int> a5 = new Node<int>();
a5.NodeValue = 12;

Node<int> a3 = new Node<int>();
a3.NodeValue = 13;

Node<int> a4 = new Node<int>();
a4.NodeValue = 14;
a1.NextNode = a2;
a2.NextNode = a3;
a3.NextNode = a4;
a4.NextNode = a5;
a5.NextNode = null;

Console.WriteLine("----------------------------------------------------");
Console.WriteLine("Reverse  List");
Reverse(ref a1);
Console.WriteLine("----------------------------------------------------");

}
public static void Reverse(ref Node<int> head)
{

Node<int> first;
Node<int> rest;
rest = first.NextNode;
if (rest == null) return;
Reverse(ref rest);
first.NextNode.NextNode = first;
first.NextNode = null;

}
{
while (temp != null)
{
Console.Write(temp.NodeValue + "-->"
);
temp = temp.NextNode;

}
Console.WriteLine();

}

}```