Skip to main content

Rotate linked list clockwise by k nodes in golang

Rotating linked list node clockwise

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

package main
import "fmt"
/*
  Go program for 
  Rotate a list by moving each element 
  k times to the right.
  Or clockwise rotation of 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
    tail * LinkNode
}
func getSingleLL() * SingleLL {
    // return new SingleLL
    return &SingleLL {
        nil,
        nil,
    }
}
// Add new Node at end of linked list 
func(this *SingleLL) addNode(data int) {
    var node * LinkNode = getLinkNode(data)
    if this.head == nil {
        this.head = node
    } else {
        // Append the node at last position
        this.tail.next = node
    }
    this.tail = node
}
// Display linked list element
func(this SingleLL) display() {
    if this.head == nil {
        fmt.Println("\n Empty linked list")
        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 are perform the linked list rotation
func(this *SingleLL) rotation(k int) {
    // Define some auxiliary variable
    var auxiliary * LinkNode = this.head
    var count int = 0
    // Count number of node in linked list
    for (auxiliary != nil) {
        // 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
    for (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 = nil
}
// Handles the request to perform rotation
// k is indicate node rotation
func(this SingleLL) clockwiseRotation(k int) {
    if k <= 0 {
        // When invalid given k
        return
    }
    if this.head == nil {
        fmt.Println("\n Empty Linked List")
        return
    }
    // Display given linked list
    fmt.Println(" Before rotate ")
    fmt.Println(" Linked List : ")
    this.display()
    fmt.Println(" Given k : ", k)
    // Perform rotation
    this.rotation(k)
    // Display resultant linked list
    fmt.Println(" After rotate ")
    fmt.Println(" Linked List : ")
    this.display()
    fmt.Println("\n")
}
func main() {
    var sll1 * SingleLL = getSingleLL()
    var sll2 * SingleLL = getSingleLL()
    // 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)
}

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