Skip to main content

Rotate linked list clockwise by k nodes in php

Rotating linked list node clockwise

Php program for Rotate linked list clockwise by k nodes. Here mentioned other language solution.

<?php
/*
  Php program for 
  Rotate a list by moving each element 
  k times to the right.
  Or clockwise rotation of linked list 
*/
// Linked list node
class LinkNode
{
	public $data;
	public $next;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->next = NULL;
	}
}
class SingleLL
{
	public $head;
	public $tail;
	public	function __construct()
	{
		$this->head = NULL;
		$this->tail = NULL;
	}
	// Add new Node at end of linked list 
	public	function addNode($data)
	{
		$node = new LinkNode($data);
		if ($this->head == NULL)
		{
			$this->head = $node;
		}
		else
		{
			// Append the node at last position
			$this->tail->next = $node;
		}
		$this->tail = $node;
	}
	// Display linked list element
	public	function display()
	{
		if ($this->head == NULL)
		{
			echo "\n Empty linked list\n";
			return;
		}
		$temp = $this->head;
		// iterating linked list elements
		while ($temp != NULL)
		{
			echo " ".($temp->data)." →";
			// Visit to next node
			$temp = $temp->next;
		}
		echo " NULL\n";
	}
	// This are perform the linked list rotation
	public	function rotation($k)
	{
		// Define some auxiliary variable
		$auxiliary = $this->head;
		$count = 0;
		// Count number of node in linked list
		while ($auxiliary != NULL)
		{
			// visit to next node
			$auxiliary = $auxiliary->next;
			$count++;
		}
		if ($count <= 1)
		{
			// When have less than 2 nodes in linked list
			return;
		}
		// Get actual rotation
		$count = $k % $count;
		if ($count == 0)
		{
			// When actual linked list are not affected
			return;
		}
		$auxiliary = $this->head;
		// Find the rotational node
		while ($count > 1)
		{
			// Visit to next node
			$auxiliary = $auxiliary->next;
			$count--;
		}
		// Connecting the last node to first node of linked list
		$this->tail->next = $this->head;
		// Set new last node
		$this->tail = $auxiliary;
		// Set new head
		$this->head = $auxiliary->next;
		// Set that there is no node after of tail
		$this->tail->next = NULL;
	}
	// Handles the request to perform rotation
	// k is indicate node rotation
	public	function clockwiseRotation($k)
	{
		if ($k <= 0)
		{
			// When invalid given k
			return;
		}
		if ($this->head == NULL)
		{
			echo "\n Empty Linked List\n";
			return;
		}
		// Display given linked list
		echo " Before rotate \n";
		echo " Linked List : \n";
		$this->display();
		echo " Given k : $k \n";
		// Perform rotation
		$this->rotation($k);
		// Display resultant linked list
		echo " After rotate \n";
		echo " Linked List : \n";
		$this->display();
		echo "\n\n";
	}
	public static function main()
	{
		$sll1 = new SingleLL();
		$sll2 = new SingleLL();
		// First linked list
		// 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
		$sll1->addNode(1);
		$sll1->addNode(2);
		$sll1->addNode(3);
		$sll1->addNode(4);
		$sll1->addNode(5);
		$sll1->addNode(6);
		$sll1->addNode(7);
		$sll1->addNode(8);
		// Second linked list
		// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
		$sll2->addNode(4);
		$sll2->addNode(9);
		$sll2->addNode(7);
		$sll2->addNode(3);
		$sll2->addNode(8);
		$sll2->addNode(6);
		$sll2->addNode(-2);
		// Test case
		$sll1->clockwiseRotation(3);
		$sll2->clockwiseRotation(18);
	}
}
SingleLL::main();

Output

 Before rotate
 Linked List :
 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
 Given k : 3
 After rotate
 Linked List :
 4 → 5 → 6 → 7 → 8 → 1 → 2 → 3 → NULL


 Before rotate
 Linked List :
 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
 Given k : 18
 After rotate
 Linked List :
 8 → 6 → -2 → 4 → 9 → 7 → 3 → 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