Skip to main content

Flatten a folded linked list in golang

Go program for Flatten a folded linked list. Here problem description and other solutions.

package main
import "fmt"
/*
  Go program for
  Unfold a folded linked list OR
  flatten folded linked list
*/
// Linked list node
type LinkNode struct {
	data int
	next * LinkNode
}
func getLinkNode(data int) * LinkNode {
	// return new LinkNode
	return &LinkNode {
		data,
		nil,
	}
}
type SingleLL struct {
	head * LinkNode
}
func getSingleLL() * SingleLL {
	// return new SingleLL
	return &SingleLL {
		nil,
	}
}
// Insert node at the beginning of linked list
func(this *SingleLL) addNode(data int) {
	// Create node
	var node * LinkNode = getLinkNode(data)
	node.next = this.head
	// Set new head
	this.head = node
}
// Display linked list element
func(this SingleLL) display() {
	if this.head == nil {
		return
	}
	var temp * LinkNode = this.head
	// iterating linked list elements
	for (temp != nil) {
		fmt.Print(" ", temp.data, " →")
		// Visit to next node
		temp = temp.next
	}
	fmt.Println(" NULL")
}
// This is handle the request of unfold given linked list nodes
func(this SingleLL) unfoldList() {
	if this.head == nil {
		fmt.Println("\n Empty linked list")
		return
	}
	var temp * LinkNode = this.head
	var auxiliary * LinkNode = nil
	var hold * LinkNode = nil
	// Loop which is separating the fold elements 
	for (temp.next != nil) {
		// Get the second element
		hold = temp.next
		if hold.next != nil {
			// When exists pair of three elements
			temp.next = hold.next
			// Visit to 3rd element
			temp = hold.next
		} else {
			// When get last two elements
			temp.next = nil
		}
		// Add new node at beginning of auxiliary linked list
		hold.next = auxiliary
		// Make new head node
		auxiliary = hold
	}
	if temp != nil {
		// Combine lists
		temp.next = auxiliary
	}
}
func main() {
	// Create a empty linked lists
	var sll1 * SingleLL = getSingleLL()
	var sll2 * SingleLL = getSingleLL()
	//  Constructed first linked list
	//  2 → 5 → 1 → 8 → 10 → 4 → 9 → 7 → NULL
	sll1.addNode(7)
	sll1.addNode(9)
	sll1.addNode(4)
	sll1.addNode(10)
	sll1.addNode(8)
	sll1.addNode(1)
	sll1.addNode(5)
	sll1.addNode(2)
	// Constructed second linked list
	// 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
	sll2.addNode(7)
	sll2.addNode(6)
	sll2.addNode(5)
	sll2.addNode(4)
	sll2.addNode(3)
	sll2.addNode(2)
	sll2.addNode(1)
	// Test A
	fmt.Println(" Before unfold")
	sll1.display()
	sll1.unfoldList()
	fmt.Println(" After unfold")
	sll1.display()
	// Test B
	fmt.Println(" Before unfold")
	sll2.display()
	sll2.unfoldList()
	fmt.Println(" After unfold")
	sll2.display()
}

Output

 Before unfold
 2 → 5 → 1 → 8 → 10 → 4 → 9 → 7 → NULL
 After unfold
 2 → 1 → 10 → 9 → 7 → 4 → 8 → 5 → NULL
 Before unfold
 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
 After unfold
 1 → 3 → 5 → 7 → 6 → 4 → 2 → 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