Bitonic point in the given linked list
Here given code implementation process.
// C Program
// Bitonic point in the given linked list
#include <stdio.h>
//For malloc function
#include <stdlib.h>
//Linked List Node
struct Node
{
int data;
struct Node *next;
};
//Create a node of linked list
struct Node *create_node(int data)
{
//Create dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
//Set initial node value
node->data = data;
node->next = NULL;
}
return node;
}
//Add new node at end of linked list
void insert(struct Node **head, int data)
{
struct Node *node = create_node(data);
if ( *head == NULL)
{
*head = node;
}
else
{
struct Node *temp = *head;
//Find last node
while (temp->next != NULL)
{
temp = temp->next;
}
//Add node at last possition
temp->next = node;
}
}
//Display linked list element
void display(struct Node *head)
{
if (head == NULL)
{
printf("\nEmpty linked list\n");
return;
}
struct Node *temp = head;
//iterating linked list elements
while (temp != NULL)
{
if (temp != head)
{
printf(" →");
}
printf(" %d", temp->data);
//visit to next node
temp = temp->next;
}
printf(" → NULL");
}
//Find a valid bitonic point in given linked list node sequence
void bitonic_point(struct Node *head)
{
//get first node
struct Node *point = head;
//Display linked list
printf("\n Linked List ");
display(head);
if (point == NULL || point->next == NULL || point->data > point->next->data || point->next->next == NULL)
{
//if given bitonic sequence are invalid
printf("\n Bitonic point not exist\n");
}
else
{
struct Node *result = NULL;
// increasing sequence
while (point != NULL && result == NULL && point->next != NULL)
{
if (point->data > point->next->data)
{
//This is endpoint of increasing sequence
result = point;
}
//visit to next node
point = point->next;
}
if (result != NULL && point != NULL)
{
// Check decreasing sequence
while (point != NULL && result != NULL && point->next != NULL)
{
if (point->next->data < point->data)
{
point = point->next;
}
else
{
//When bitonic sequence are not valid
result = NULL;
}
}
if (result != NULL)
{
printf("\n Bitonic point : %d\n", result->data);
}
else
{
printf("\n Bitonic point not exist\n");
}
}
else
{
//When no valid endpoint in increasing bitonic sequence
printf("\n Bitonic point not exist\n");
}
}
}
int main()
{
//Define few empty linked list
struct Node *list1 = NULL;
struct Node *list2 = NULL;
struct Node *list3 = NULL;
struct Node *list4 = NULL;
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
insert( &list1, 2);
insert( &list1, 4);
insert( &list1, 8);
insert( &list1, 9);
insert( &list1, 7);
insert( &list1, 5);
insert( &list1, 3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
insert( &list2, 1);
insert( &list2, 2);
insert( &list2, 3);
insert( &list2, 4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
insert( &list3, 1);
insert( &list3, 2);
insert( &list3, 3);
insert( &list3, 4);
insert( &list3, 1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
insert( &list4, 1);
insert( &list4, 2);
insert( &list4, 3);
insert( &list4, 4);
insert( &list4, 4);
//Test case
bitonic_point(list1);
bitonic_point(list2);
bitonic_point(list3);
bitonic_point(list4);
return 0;
}
Output
Linked List 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
// Java Program
// Bitonic point in the given linked list
//Node of LinkedList
public class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
public class MyLinkedList
{
public Node head;
public Node tail;
//Class constructor
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int data)
{
//Create a node
Node node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
public void display()
{
if (this.head == null)
{
System.out.print("\nEmpty linked list\n");
return;
}
Node temp = this.head;
System.out.print("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
System.out.print(" →");
}
System.out.print(" " + temp.data);
//visit to next node
temp = temp.next;
}
System.out.print(" → NULL");
}
//Find a valid bitonic point in given linked list node sequence
public void bitonic_point()
{
//get first node
Node point = this.head;
//Display linked list
System.out.print("\n Linked List ");
this.display();
if (point == null || point.next == null || point.data > point.next.data || point.next.next == null)
{
//if given bitonic sequence are invalid
System.out.print("\n Bitonic point not exist\n");
}
else
{
Node result = null;
// increasing sequence
while (point != null && result == null && point.next != null)
{
if (point.data > point.next.data)
{
//This is endpoint of increasing sequence
result = point;
}
//visit to next node
point = point.next;
}
if (result != null && point != null)
{
// Check decreasing sequence
while (point != null && result != null && point.next != null)
{
if (point.next.data < point.data)
{
point = point.next;
}
else
{
//When bitonic sequence are not valid
result = null;
}
}
if (result != null)
{
System.out.print("\n Bitonic point : " + result.data + "\n");
}
else
{
System.out.print("\n Bitonic point not exist\n");
}
}
else
{
//When no valid bitonic point in increasing bitonic sequence
System.out.print("\n Bitonic point not exist\n");
}
}
}
public static void main(String[] args)
{
MyLinkedList list1 = new MyLinkedList();
MyLinkedList list2 = new MyLinkedList();
MyLinkedList list3 = new MyLinkedList();
MyLinkedList list4 = new MyLinkedList();
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2);
list1.insert(4);
list1.insert(8);
list1.insert(9);
list1.insert(7);
list1.insert(5);
list1.insert(3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
list2.insert(1);
list2.insert(2);
list2.insert(3);
list2.insert(4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(3);
list3.insert(4);
list3.insert(1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1);
list4.insert(2);
list4.insert(3);
list4.insert(4);
list4.insert(4);
//Test case
list1.bitonic_point();
list2.bitonic_point();
list3.bitonic_point();
list4.bitonic_point();
}
}
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
//Include header file
#include <iostream>
using namespace std;
// C++ Program
// Bitonic point in the given linked list
//Node of LinkedList
class Node
{
public: int data;
Node *next;
Node(int data)
{
//Set node value
this->data = data;
this->next = NULL;
}
};
class MyLinkedList
{
public: Node *head;
Node *tail;
//Class constructor
MyLinkedList()
{
this->head = NULL;
this->tail = NULL;
}
//insert node at last of linke list
void insert(int data)
{
//Create a node
Node *node = new Node(data);
if (this->head == NULL)
{
//When linked list empty add first node
this->head = node;
this->tail = node;
}
else
{
//Add new node at end of linked list
this->tail->next = node;
this->tail = node;
}
}
//Display linked list element
void display()
{
if (this->head == NULL)
{
cout << "\nEmpty linked list\n";
return;
}
Node *temp = this->head;
cout << "\n Linked List : ";
//iterating linked list elements
while (temp != NULL)
{
if (temp != this->head)
{
cout << " →";
}
cout << " " << temp->data;
//visit to next node
temp = temp->next;
}
cout << " → NULL";
}
//Find a valid bitonic point in given linked list node sequence
void bitonic_point()
{
//get first node
Node *point = this->head;
//Display linked list
cout << "\n Linked List ";
this->display();
if (point == NULL || point->next == NULL || point->data > point->next->data || point->next->next == NULL)
{
//if given bitonic sequence are invalid
cout << "\n Bitonic point not exist\n";
}
else
{
Node *result = NULL;
// increasing sequence
while (point != NULL && result == NULL && point->next != NULL)
{
if (point->data > point->next->data)
{
//This is endpoint of increasing sequence
result = point;
}
//visit to next node
point = point->next;
}
if (result != NULL && point != NULL)
{
// Check decreasing sequence
while (point != NULL && result != NULL && point->next != NULL)
{
if (point->next->data < point->data)
{
point = point->next;
}
else
{
//When bitonic sequence are not valid
result = NULL;
}
}
if (result != NULL)
{
cout << "\n Bitonic point : " << result->data << "\n";
}
else
{
cout << "\n Bitonic point not exist\n";
}
}
else
{
//When no valid bitonic point in increasing bitonic sequence
cout << "\n Bitonic point not exist\n";
}
}
}
};
int main()
{
MyLinkedList list1 = MyLinkedList();
MyLinkedList list2 = MyLinkedList();
MyLinkedList list3 = MyLinkedList();
MyLinkedList list4 = MyLinkedList();
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2);
list1.insert(4);
list1.insert(8);
list1.insert(9);
list1.insert(7);
list1.insert(5);
list1.insert(3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
list2.insert(1);
list2.insert(2);
list2.insert(3);
list2.insert(4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(3);
list3.insert(4);
list3.insert(1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1);
list4.insert(2);
list4.insert(3);
list4.insert(4);
list4.insert(4);
//Test case
list1.bitonic_point();
list2.bitonic_point();
list3.bitonic_point();
list4.bitonic_point();
return 0;
}
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
//Include namespace system
using System;
// C# Program
// Bitonic point in the given linked list
//Node of LinkedList
public class Node
{
public int data;
public Node next;
public Node(int data)
{
//Set node value
this.data = data;
this.next = null;
}
}
public class MyLinkedList
{
public Node head;
public Node tail;
//Class constructor
public MyLinkedList()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
public void insert(int data)
{
//Create a node
Node node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
public void display()
{
if (this.head == null)
{
Console.Write("\nEmpty linked list\n");
return;
}
Node temp = this.head;
Console.Write("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
Console.Write(" →");
}
Console.Write(" " + temp.data);
//visit to next node
temp = temp.next;
}
Console.Write(" → NULL");
}
//Find a valid bitonic point in given linked list node sequence
public void bitonic_point()
{
//get first node
Node point = this.head;
//Display linked list
Console.Write("\n Linked List ");
this.display();
if (point == null || point.next == null || point.data > point.next.data || point.next.next == null)
{
//if given bitonic sequence are invalid
Console.Write("\n Bitonic point not exist\n");
}
else
{
Node result = null;
// increasing sequence
while (point != null && result == null && point.next != null)
{
if (point.data > point.next.data)
{
//This is endpoint of increasing sequence
result = point;
}
//visit to next node
point = point.next;
}
if (result != null && point != null)
{
// Check decreasing sequence
while (point != null && result != null && point.next != null)
{
if (point.next.data < point.data)
{
point = point.next;
}
else
{
//When bitonic sequence are not valid
result = null;
}
}
if (result != null)
{
Console.Write("\n Bitonic point : " + result.data + "\n");
}
else
{
Console.Write("\n Bitonic point not exist\n");
}
}
else
{
//When no valid bitonic point in increasing bitonic sequence
Console.Write("\n Bitonic point not exist\n");
}
}
}
public static void Main(String[] args)
{
MyLinkedList list1 = new MyLinkedList();
MyLinkedList list2 = new MyLinkedList();
MyLinkedList list3 = new MyLinkedList();
MyLinkedList list4 = new MyLinkedList();
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2);
list1.insert(4);
list1.insert(8);
list1.insert(9);
list1.insert(7);
list1.insert(5);
list1.insert(3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
list2.insert(1);
list2.insert(2);
list2.insert(3);
list2.insert(4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(3);
list3.insert(4);
list3.insert(1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1);
list4.insert(2);
list4.insert(3);
list4.insert(4);
list4.insert(4);
//Test case
list1.bitonic_point();
list2.bitonic_point();
list3.bitonic_point();
list4.bitonic_point();
}
}
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
<?php
// Php Program
// Bitonic point in the given linked list
//Node of LinkedList
class Node
{
public $data;
public $next;
function __construct($data)
{
//Set node value
$this->data = $data;
$this->next = null;
}
}
class MyLinkedList
{
public $head;
public $tail;
//Class constructor
function __construct()
{
$this->head = null;
$this->tail = null;
}
//insert node at last of linke list
public function insert($data)
{
//Create a node
$node = new Node($data);
if ($this->head == null)
{
//When linked list empty add first node
$this->head = $node;
$this->tail = $node;
}
else
{
//Add new node at end of linked list
$this->tail->next = $node;
$this->tail = $node;
}
}
//Display linked list element
public function display()
{
if ($this->head == null)
{
echo "\nEmpty linked list\n";
return;
}
$temp = $this->head;
echo "\n Linked List : ";
//iterating linked list elements
while ($temp != null)
{
if ($temp != $this->head)
{
echo " →";
}
echo " ". $temp->data;
//visit to next node
$temp = $temp->next;
}
echo " → NULL";
}
//Find a valid bitonic point in given linked list node sequence
public function bitonic_point()
{
//get first node
$point = $this->head;
//Display linked list
echo "\n Linked List ";
$this->display();
if ($point == null || $point->next == null || $point->data > $point->next->data || $point->next->next == null)
{
//if given bitonic sequence are invalid
echo "\n Bitonic point not exist\n";
}
else
{
$result = null;
// increasing sequence
while ($point != null && $result == null && $point->next != null)
{
if ($point->data > $point->next->data)
{
//This is endpoint of increasing sequence
$result = $point;
}
//visit to next node
$point = $point->next;
}
if ($result != null && $point != null)
{
// Check decreasing sequence
while ($point != null && $result != null && $point->next != null)
{
if ($point->next->data < $point->data)
{
$point = $point->next;
}
else
{
//When bitonic sequence are not valid
$result = null;
}
}
if ($result != null)
{
echo "\n Bitonic point : ". $result->data ."\n";
}
else
{
echo "\n Bitonic point not exist\n";
}
}
else
{
//When no valid bitonic point in increasing bitonic sequence
echo "\n Bitonic point not exist\n";
}
}
}
}
function main()
{
$list1 = new MyLinkedList();
$list2 = new MyLinkedList();
$list3 = new MyLinkedList();
$list4 = new MyLinkedList();
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
$list1->insert(2);
$list1->insert(4);
$list1->insert(8);
$list1->insert(9);
$list1->insert(7);
$list1->insert(5);
$list1->insert(3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
$list2->insert(1);
$list2->insert(2);
$list2->insert(3);
$list2->insert(4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
$list3->insert(1);
$list3->insert(2);
$list3->insert(3);
$list3->insert(4);
$list3->insert(1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
$list4->insert(1);
$list4->insert(2);
$list4->insert(3);
$list4->insert(4);
$list4->insert(4);
//Test case
$list1->bitonic_point();
$list2->bitonic_point();
$list3->bitonic_point();
$list4->bitonic_point();
}
main();
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
// Node Js Program
// Bitonic point in the given linked list
//Node of LinkedList
class Node
{
constructor(data)
{
//Set node value
this.data = data;
this.next = null;
}
}
class MyLinkedList
{
//Class constructor
constructor()
{
this.head = null;
this.tail = null;
}
//insert node at last of linke list
insert(data)
{
//Create a node
var node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
display()
{
if (this.head == null)
{
process.stdout.write("\nEmpty linked list\n");
return;
}
var temp = this.head;
process.stdout.write("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
process.stdout.write(" →");
}
process.stdout.write(" " + temp.data);
//visit to next node
temp = temp.next;
}
process.stdout.write(" → NULL");
}
//Find a valid bitonic point in given linked list node sequence
bitonic_point()
{
//get first node
var point = this.head;
//Display linked list
process.stdout.write("\n Linked List ");
this.display();
if (point == null || point.next == null || point.data > point.next.data || point.next.next == null)
{
//if given bitonic sequence are invalid
process.stdout.write("\n Bitonic point not exist\n");
}
else
{
var result = null;
// increasing sequence
while (point != null && result == null && point.next != null)
{
if (point.data > point.next.data)
{
//This is endpoint of increasing sequence
result = point;
}
//visit to next node
point = point.next;
}
if (result != null && point != null)
{
// Check decreasing sequence
while (point != null && result != null && point.next != null)
{
if (point.next.data < point.data)
{
point = point.next;
}
else
{
//When bitonic sequence are not valid
result = null;
}
}
if (result != null)
{
process.stdout.write("\n Bitonic point : " + result.data + "\n");
}
else
{
process.stdout.write("\n Bitonic point not exist\n");
}
}
else
{
//When no valid bitonic point in increasing bitonic sequence
process.stdout.write("\n Bitonic point not exist\n");
}
}
}
}
function main()
{
var list1 = new MyLinkedList();
var list2 = new MyLinkedList();
var list3 = new MyLinkedList();
var list4 = new MyLinkedList();
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2);
list1.insert(4);
list1.insert(8);
list1.insert(9);
list1.insert(7);
list1.insert(5);
list1.insert(3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
list2.insert(1);
list2.insert(2);
list2.insert(3);
list2.insert(4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(3);
list3.insert(4);
list3.insert(1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1);
list4.insert(2);
list4.insert(3);
list4.insert(4);
list4.insert(4);
//Test case
list1.bitonic_point();
list2.bitonic_point();
list3.bitonic_point();
list4.bitonic_point();
}
main();
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
# Python 3 Program
# Bitonic point in the given linked list
# Node of LinkedList
class Node :
def __init__(self, data) :
# Set node value
self.data = data
self.next = None
class MyLinkedList :
# Class constructor
def __init__(self) :
self.head = None
self.tail = None
# insert node at last of linke list
def insert(self, data) :
# Create a node
node = Node(data)
if (self.head == None) :
# When linked list empty add first node
self.head = node
self.tail = node
else :
# Add new node at end of linked list
self.tail.next = node
self.tail = node
# Display linked list element
def display(self) :
if (self.head == None) :
print("\nEmpty linked list\n", end = "")
return
temp = self.head
print("\n Linked List : ", end = "")
# iterating linked list elements
while (temp != None) :
if (temp != self.head) :
print(" →", end = "")
print(" ", temp.data, end = "")
# visit to next node
temp = temp.next
print(" → NULL", end = "")
# Find a valid bitonic point in given linked list node sequence
def bitonic_point(self) :
# get first node
point = self.head
# Display linked list
print("\n Linked List ", end = "")
self.display()
if (point == None or point.next == None or point.data > point.next.data or point.next.next == None) :
# if given bitonic sequence are invalid
print("\n Bitonic point not exist\n", end = "")
else :
result = None
# increasing sequence
while (point != None and result == None and point.next != None) :
if (point.data > point.next.data) :
# This is endpoint of increasing sequence
result = point
# visit to next node
point = point.next
if (result != None and point != None) :
# Check decreasing sequence
while (point != None and result != None and point.next != None) :
if (point.next.data < point.data) :
point = point.next
else :
# When bitonic sequence are not valid
result = None
if (result != None) :
print("\n Bitonic point : ", result.data ,"\n", end = "")
else :
print("\n Bitonic point not exist\n", end = "")
else :
# When no valid bitonic point in increasing bitonic sequence
print("\n Bitonic point not exist\n", end = "")
def main() :
list1 = MyLinkedList()
list2 = MyLinkedList()
list3 = MyLinkedList()
list4 = MyLinkedList()
# Add node in first linked list
# 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2)
list1.insert(4)
list1.insert(8)
list1.insert(9)
list1.insert(7)
list1.insert(5)
list1.insert(3)
# Add node in second linked list
# 1 → 2 → 3 → 4 → NULL
list2.insert(1)
list2.insert(2)
list2.insert(3)
list2.insert(4)
# Add node in third linked list
# 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1)
list3.insert(2)
list3.insert(3)
list3.insert(4)
list3.insert(1)
# Add node in fourth linked list
# 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1)
list4.insert(2)
list4.insert(3)
list4.insert(4)
list4.insert(4)
# Test case
list1.bitonic_point()
list2.bitonic_point()
list3.bitonic_point()
list4.bitonic_point()
if __name__ == "__main__": main()
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
# Ruby Program
# Bitonic point in the given linked list
# Node of LinkedList
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
# Set node value
self.data = data
self.next = nil
end
end
class MyLinkedList
# Define the accessor and reader of class MyLinkedList
attr_reader :head, :tail
attr_accessor :head, :tail
# Class constructor
def initialize()
self.head = nil
self.tail = nil
end
# insert node at last of linke list
def insert(data)
# Create a node
node = Node.new(data)
if (self.head == nil)
# When linked list empty add first node
self.head = node
self.tail = node
else
# Add new node at end of linked list
self.tail.next = node
self.tail = node
end
end
# Display linked list element
def display()
if (self.head == nil)
print("\nEmpty linked list\n")
return
end
temp = self.head
print("\n Linked List : ")
# iterating linked list elements
while (temp != nil)
if (temp != self.head)
print(" →")
end
print(" ", temp.data)
# visit to next node
temp = temp.next
end
print(" → NULL")
end
# Find a valid bitonic point in given linked list node sequence
def bitonic_point()
# get first node
point = self.head
# Display linked list
print("\n Linked List ")
self.display()
if (point == nil || point.next == nil || point.data > point.next.data || point.next.next == nil)
# if given bitonic sequence are invalid
print("\n Bitonic point not exist\n")
else
result = nil
# increasing sequence
while (point != nil && result == nil && point.next != nil)
if (point.data > point.next.data)
# This is endpoint of increasing sequence
result = point
end
# visit to next node
point = point.next
end
if (result != nil && point != nil)
# Check decreasing sequence
while (point != nil && result != nil && point.next != nil)
if (point.next.data < point.data)
point = point.next
else
# When bitonic sequence are not valid
result = nil
end
end
if (result != nil)
print("\n Bitonic point : ", result.data ,"\n")
else
print("\n Bitonic point not exist\n")
end
else
# When no valid bitonic point in increasing bitonic sequence
print("\n Bitonic point not exist\n")
end
end
end
end
def main()
list1 = MyLinkedList.new()
list2 = MyLinkedList.new()
list3 = MyLinkedList.new()
list4 = MyLinkedList.new()
# Add node in first linked list
# 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2)
list1.insert(4)
list1.insert(8)
list1.insert(9)
list1.insert(7)
list1.insert(5)
list1.insert(3)
# Add node in second linked list
# 1 → 2 → 3 → 4 → NULL
list2.insert(1)
list2.insert(2)
list2.insert(3)
list2.insert(4)
# Add node in third linked list
# 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1)
list3.insert(2)
list3.insert(3)
list3.insert(4)
list3.insert(1)
# Add node in fourth linked list
# 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1)
list4.insert(2)
list4.insert(3)
list4.insert(4)
list4.insert(4)
# Test case
list1.bitonic_point()
list2.bitonic_point()
list3.bitonic_point()
list4.bitonic_point()
end
main()
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
// Scala Program
// Bitonic point in the given linked list
//Node of LinkedList
class Node(var data: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
class MyLinkedList(var head: Node,
var tail: Node)
{
//Class constructor
def this()
{
this(null, null);
}
//insert node at last of linke list
def insert(data: Int): Unit = {
//Create a node
var node: Node = new Node(data);
if (this.head == null)
{
//When linked list empty add first node
this.head = node;
this.tail = node;
}
else
{
//Add new node at end of linked list
this.tail.next = node;
this.tail = node;
}
}
//Display linked list element
def display(): Unit = {
if (this.head == null)
{
print("\nEmpty linked list\n");
return;
}
var temp: Node = this.head;
print("\n Linked List : ");
//iterating linked list elements
while (temp != null)
{
if (temp != this.head)
{
print(" →");
}
print(" " + temp.data);
//visit to next node
temp = temp.next;
}
print(" → NULL");
}
//Find a valid bitonic point in given linked list node sequence
def bitonic_point(): Unit = {
//get first node
var point: Node = this.head;
//Display linked list
print("\n Linked List ");
this.display();
if (point == null || point.next == null || point.data > point.next.data || point.next.next == null)
{
//if given bitonic sequence are invalid
print("\n Bitonic point not exist\n");
}
else
{
var result: Node = null;
// increasing sequence
while (point != null && result == null && point.next != null)
{
if (point.data > point.next.data)
{
//This is endpoint of increasing sequence
result = point;
}
//visit to next node
point = point.next;
}
if (result != null && point != null)
{
// Check decreasing sequence
while (point != null && result != null && point.next != null)
{
if (point.next.data < point.data)
{
point = point.next;
}
else
{
//When bitonic sequence are not valid
result = null;
}
}
if (result != null)
{
print("\n Bitonic point : " + result.data + "\n");
}
else
{
print("\n Bitonic point not exist\n");
}
}
else
{
//When no valid bitonic point in increasing bitonic sequence
print("\n Bitonic point not exist\n");
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var list1: MyLinkedList = new MyLinkedList();
var list2: MyLinkedList = new MyLinkedList();
var list3: MyLinkedList = new MyLinkedList();
var list4: MyLinkedList = new MyLinkedList();
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2);
list1.insert(4);
list1.insert(8);
list1.insert(9);
list1.insert(7);
list1.insert(5);
list1.insert(3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
list2.insert(1);
list2.insert(2);
list2.insert(3);
list2.insert(4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(3);
list3.insert(4);
list3.insert(1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1);
list4.insert(2);
list4.insert(3);
list4.insert(4);
list4.insert(4);
//Test case
list1.bitonic_point();
list2.bitonic_point();
list3.bitonic_point();
list4.bitonic_point();
}
}
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
// Swift Program
// Bitonic point in the given linked list
//Node of LinkedList
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
//Set node value
self.data = data;
self.next = nil;
}
}
class MyLinkedList
{
var head: Node? ;
var tail: Node? ;
//Class constructor
init()
{
self.head = nil;
self.tail = nil;
}
//insert node at last of linke list
func insert(_ data: Int)
{
//Create a node
let node: Node? = Node(data);
if (self.head == nil)
{
//When linked list empty add first node
self.head = node;
self.tail = node;
}
else
{
//Add new node at end of linked list
self.tail!.next = node;
self.tail = node;
}
}
//Display linked list element
func display()
{
if (self.head == nil)
{
print("\nEmpty linked list\n", terminator: "");
return;
}
var temp: Node? = self.head;
print("\n Linked List : ", terminator: "");
//iterating linked list elements
while (temp != nil)
{
if (!(temp === self.head))
{
print(" →", terminator: "");
}
print(" ", temp!.data, terminator: "");
//visit to next node
temp = temp!.next;
}
print(" → NULL", terminator: "");
}
//Find a valid bitonic point in given linked list node sequence
func bitonic_point()
{
//get first node
var point: Node? = self.head;
//Display linked list
print("\n Linked List ", terminator: "");
self.display();
if (point == nil || point!.next == nil || point!.data > point!.next!.data || point!.next!.next == nil)
{
//if given bitonic sequence are invalid
print("\n Bitonic point not exist\n", terminator: "");
}
else
{
var result: Node? = nil;
// increasing sequence
while (point != nil && result == nil && point!.next != nil)
{
if (point!.data > point!.next!.data)
{
//This is endpoint of increasing sequence
result = point;
}
//visit to next node
point = point!.next;
}
if (result != nil && point != nil)
{
// Check decreasing sequence
while (point != nil && result != nil && point!.next != nil)
{
if (point!.next!.data < point!.data)
{
point = point!.next;
}
else
{
//When bitonic sequence are not valid
result = nil;
}
}
if (result != nil)
{
print("\n Bitonic point : ", result!.data ,"\n", terminator: "");
}
else
{
print("\n Bitonic point not exist\n", terminator: "");
}
}
else
{
//When no valid bitonic point in increasing bitonic sequence
print("\n Bitonic point not exist\n", terminator: "");
}
}
}
}
func main()
{
let list1: MyLinkedList = MyLinkedList();
let list2: MyLinkedList = MyLinkedList();
let list3: MyLinkedList = MyLinkedList();
let list4: MyLinkedList = MyLinkedList();
//Add node in first linked list
// 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
list1.insert(2);
list1.insert(4);
list1.insert(8);
list1.insert(9);
list1.insert(7);
list1.insert(5);
list1.insert(3);
//Add node in second linked list
// 1 → 2 → 3 → 4 → NULL
list2.insert(1);
list2.insert(2);
list2.insert(3);
list2.insert(4);
//Add node in third linked list
// 1 → 2 → 3 → 4 → 1 → NULL
list3.insert(1);
list3.insert(2);
list3.insert(3);
list3.insert(4);
list3.insert(1);
//Add node in fourth linked list
// 1 → 2 → 3 → 4 → 4 → NULL
list4.insert(1);
list4.insert(2);
list4.insert(3);
list4.insert(4);
list4.insert(4);
//Test case
list1.bitonic_point();
list2.bitonic_point();
list3.bitonic_point();
list4.bitonic_point();
}
main();
Output
Linked List
Linked List : 2 → 4 → 8 → 9 → 7 → 5 → 3 → NULL
Bitonic point : 9
Linked List
Linked List : 1 → 2 → 3 → 4 → NULL
Bitonic point not exist
Linked List
Linked List : 1 → 2 → 3 → 4 → 1 → NULL
Bitonic point : 4
Linked List
Linked List : 1 → 2 → 3 → 4 → 4 → NULL
Bitonic point not exist
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