how to sort a linked list using golang Online study

In this post i am going to sort the singly linked list in increment order.In earlier linked list post, i implemented how to create a linked list using golang. Please check that post if you need more information on linked list.

 

There are two ways to sort the linked list one is the sort only data of the linked list without making and changes in the list pointer and other algorithm which come is like without changing the data we can make the pointer and link them accordingly in both case first we need to create a linked list using go and then we apply sort algorithm on that.

After sorting the list:

Let Jump on the implementation part.

So basically we are going to implement sorting the linked list node with changing pointer value, so in this case we are implementing mechanism so based on pointer our list is rearrange like we do in insertion sort and based on its value, it will fit on its given location.

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 (lstVal *LL) deleteFromBeginning() {
	if nil != lstVal && nil != lstVal.list {
		head := lstVal.list
		lstVal.list = head.next
		head = nil
	}
}

func sort(ll *linklist, insertedNode *linklist) *linklist {
	head := ll
	if ll.val > insertedNode.val {
		insertedNode.next = ll
		ll = insertedNode
	} else {
		for head.next != nil && head.next.val < insertedNode.val {
			head = head.next
		}
		insertedNode.next = head.next
		head.next = insertedNode
	}
	return ll
}

func sortTheLinkedList(ll *linklist) *linklist {
	head := ll
	sortedList := new(linklist)
	var firstTime bool = true
	for head != nil {
		nextNode := head.next
		if firstTime {
			sortedList = head
			sortedList.next = nil
			firstTime = false
		} else {
			sortedList = sort(sortedList, head)
		}
		head = nextNode
	}
	return sortedList
}

func main() {
	staticList := []int{5, 7, 1, 3, 4, 9}
	linklst := new(LL)
	for _, value := range staticList {
		linklst.insertAtBeginning(value)
	}
	fmt.Println("PrintList")
	linklst.printList()
	linklst.list = sortTheLinkedList(linklst.list)
	fmt.Println("After Sorting PrintList")
	linklst.printList()
}

 

 

 In above code, we are have added detail about insertion, printing the list and sorting the list.

Please check above code and let us know in comment if have any doubt or query.