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
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