Skip to main content

Clone a linked list with random fields in php

Php program for Clone a linked list with random fields. Here problem description and explanation.

<?php
// Php Program
// Clone a linked list with next and random field

// Linked List Node
class LinkNode
{
	public $data;
	public $next;
	public $random;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->next = NULL;
		$this->random = NULL;
	}
}
class MyLinkedList
{
	public $head;
	public	function __construct()
	{
		$this->head = NULL;
	}
	// Add new node at the end of linked list
	public	function insert($value)
	{
		// Create a node
		$node = new LinkNode($value);
		if ($this->head == NULL)
		{
			$this->head = $node;
		}
		else
		{
			$temp = $this->head;
			// Find last node
			while ($temp->next != NULL)
			{
				// Visit to next node
				$temp = $temp->next;
			}
			// Add node at last position
			$temp->next = $node;
		}
	}
	// Display linked list element
	public	function display()
	{
		if ($this->head == NULL)
		{
			echo "\nEmpty linked list\n";
			return;
		}
		$temp = $this->head;
		echo "\n ";
		while ($temp != NULL)
		{
			if ($temp != $this->head)
			{
				echo "--->";
			}
			if ($temp->random != NULL)
			{
				echo strval($temp->data).
				"(".strval($temp->random->data).
				")";
			}
			else
			{
				printf("%d", $temp->data);
			}
			$temp = $temp->next;
		}
		echo "-->NULL", "\n";
	}
	// Clone the linked list  with next and random field
	public	function cloneList()
	{
		if ($this->head == NULL)
		{
			return NULL;
		}
		// Define some auxiliary variable
		$temp = NULL;
		$current = $this->head;
		$node = NULL;
		$front = NULL;
		// Step 1
		// Create and combine clone node
		while ($current != NULL)
		{
			//Get current node of actual linked list
			$temp = $current;
			// Create clone node
			$node = new LinkNode($current->data);
			// Visit to next node
			$current = $current->next;
			// Connect clone node after actual node
			$temp->next = $node;
			// Binding this clone to next upcoming
			// nodes in actual linked list
			$node->next = $current;
		}
		// Start to actual linked list
		$current = $this->head;
		// Step 2
		// Set actual value of random field in clone linked list
		while ($current != NULL && $current->next != NULL)
		{
			// Clone list node
			$node = $current->next;
			if ($current->random != NULL)
			{
				// Set random node in clone linked list
				$node->random = $current->random->next;
			}
			// Visit to actual linked list next node
			$current = $node->next;
		}
		// Agian start to actual linked list
		$current = $this->head;
		// Step 3
		// Separate actual and clone linked list
		while ($current != NULL)
		{
			$node = $current->next;
			if ($front == NULL)
			{
				// Get first node of clone linked list
				$front = $node;
			}
			$current->next = $node->next;
			$current = $current->next;
			if ($current != NULL)
			{
				$node->next = $current->next;
			}
			else
			{
				$node->next = NULL;
			}
		}
		return $front;
	}
	public static function main($args)
	{
		// Test linked list
		$list1 = new MyLinkedList();
		$list2 = new MyLinkedList();
		// Create Normal linked list
		$list1->insert(5);
		$list1->insert(6);
		$list1->insert(1);
		$list1->insert(8);
		$list1->insert(7);
		/*
		   Simple linked list
		   5 → 6 → 1 → 8 → 7 → NULL
		   Set random node value
		   ╷───────────┐
		   │           │
		   │   ╷───────│───┐
		   ↓───│───╷   │   │
		   ↓   ↓   ↑   │   │
		   5 → 6 → 1 → 8 → 7 → NULL
		   │   │       ↑   │
		   └───│───────┘   │    
		       │           │
		       └───────────┘ 
		    5(8)-->6(7)-->1(5)-->8(5)-->7(6)-->NULL
		    Linked list with random field
		*/
		// 5-->8
		$list1->head->random = $list1->head->next->next->next;
		// 6-->7
		$list1->head->next->random = $list1->head->next->next->next->next;
		// 1 --> 5
		$list1->head->next->next->random = $list1->head;
		// 8 --> 5
		$list1->head->next->next->next->random = $list1->head;
		// 7 --> 6
		$list1->head->next->next->next->next->random = $list1->head->next;
		$list2->head = $list1->cloneList();
		echo "\n Actual Linked List";
		$list1->display();
		echo "\n Clone Linked List";
		$list2->display();
	}
}
MyLinkedList::main(array());

Output

 Actual Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL

 Clone Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->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