Skip to main content

Clone a linked list with next and random pointer in golang

Go program for Clone a linked list with random fields. Here problem description and other solutions.

package main
import "fmt"
// Go Program
// Clone a linked list with next and random pointer

// Linked List Node
type LinkNode struct {
	data int
	next * LinkNode
	random * LinkNode
}
func getLinkNode(data int) * LinkNode {
	// return new LinkNode
	return &LinkNode {
		data,
		nil,
		nil,
	}
}
type MyLinkedList struct {
	head * LinkNode
}
func getMyLinkedList() * MyLinkedList {
	// return new MyLinkedList
	return &MyLinkedList {
		nil,
	}
}
// Add new node at the end of linked list
func(this *MyLinkedList) insert(value int) {
	// Create  node
	var node * LinkNode = getLinkNode(value)
	if this.head == nil {
		this.head = node
	} else {
		var temp * LinkNode = this.head
		// Find last node
		for (temp.next != nil) {
			// Visit to next node
			temp = temp.next
		}
		// Add node at last position
		temp.next = node
	}
}
// Display linked list element
func(this MyLinkedList) display() {
	if this.head == nil {
		fmt.Print("\nEmpty linked list\n")
		return
	}
	var temp * LinkNode = this.head
	fmt.Print("\n ")
	for (temp != nil) {
		if temp != this.head {
			fmt.Print("--->")
		}
		if temp.random != nil {
			fmt.Print(temp.data, "(", temp.random.data, ")")
		} else {
			fmt.Print(temp.data)
		}
		temp = temp.next
	}
	fmt.Println("-->NULL")
}
// Clone the linked list  with next and random field
func(this MyLinkedList) cloneList() * LinkNode {
	if this.head == nil {
		return nil
	}
	// Define some auxiliary variable
	var temp * LinkNode = nil
	var current * LinkNode = this.head
	var node * LinkNode = nil
	var front * LinkNode = nil
	// Step 1
	// Create and combine clone node
	for (current != nil) {
		//Get current node of actual linked list
		temp = current
		// Create clone node
		node = getLinkNode(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
	for (current != nil && current.next != nil) {
		// Clone list node
		node = current.next
		if current.random != nil {
			// 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
	for (current != nil) {
		node = current.next
		if front == nil {
			// Get first node of clone linked list
			front = node
		}
		current.next = node.next
		current = current.next
		if current != nil {
			node.next = current.next
		} else {
			node.next = nil
		}
	}
	return front
}
func main() {
	// Test linked list
	var list1 * MyLinkedList = getMyLinkedList()
	var list2 * MyLinkedList = getMyLinkedList()
	// 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()
	fmt.Print("\n Actual Linked List")
	list1.display()
	fmt.Print("\n Clone Linked List")
	list2.display()
}

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