Posted on by Kalkicode
Code Single linked list

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

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