Reverse a linked list recursively using Go or golang

In previous post we see implementation of reverse a linked list without recursion, in that solution we use second pointer to reverse the linked list. Here we are going to use recursion to reverse linked list.

Its very important question which help interviewer to know about thier candidate knowledge. As a candidate recursive program is very helpful and its help us to give more understanding to understand the flow of program.

Recursion is widely used in dynamic programming and tree related question which we going to discuss later.

Algorithm Approach:

1.  Recursively call the next node till we not reach the end of the node
2.  Return the pointer of next node to his previous(current) node and then make the previous node as the next node of returned node and then returning the current node. 

Code:

 

package main

import (
	"fmt"
)

//Create prototype

//LL container which going to store list
type LL struct {
	list *linklist
}

//linklist for value and next pointer details
type linklist struct {
	val  int
	next *linklist
}

// createNode use for create node for list
func createNode(value int) *linklist {
	return &linklist{
		val:  value,
		next: nil,
	}
}

func (lstVal *LL) insertAtBeginning(data int) {
	if nil == lstVal.list {
		lstVal.list = createNode(data)
		return
	}

	tempNode := createNode(data)
	head := lstVal.list
	tempNode.next = head
	lstVal.list = tempNode
}

func (lstVal *LL) printList() {
	if nil != lstVal && nil != lstVal.list {
		head := lstVal.list
		for nil != head {
			fmt.Printf(" %d", head.val)
			head = head.next
		}
	}
	fmt.Println()
}

func recursiveReverseList(ll *linklist) *linklist {
	if ll == nil {
		return ll
	}
	if ll.next == nil {
		return ll
	}
	tempNode := recursiveReverseList(ll.next)
	ll.next.next = ll
	ll.next = nil
	return tempNode
}

func main() {
	staticList := []int{5, 7, 1, 3, 4, 9}
	linklst := new(LL)
	//linklst.list = new(linklist)
	//var firstTime bool = true
	for _, value := range staticList {
		linklst.insertAtBeginning(value)
	}
	fmt.Println("PrintList")
	linklst.printList()
	fmt.Println("Recursive test: ")
	linklst.list = recursiveReverseList(linklst.list)
	fmt.Println("After recursive sort: ")
	linklst.printList()
}

 

 

In above program we use recursion method to reverse the linked list using go, let me know in comment if you have question regarding this program.

You can check other post related to linked list , algorithm dynamic programming and data structure.