find the median of all nodes in a linked list in go

To find the median of all nodes in a linked list, we need to follow these steps:

Traverse the linked list to count the number of nodes.
Traverse the linked list again and add the values to an array.
Sort the array.
Calculate the median based on the number of nodes.

Here's the Go code for the same:


main.go
package main

import (
	"fmt"
	"sort"
)

type Node struct {
	value int
	next  *Node
}

func addNode(head *Node, value int) *Node {
	node := &Node{value: value, next: nil}

	if head == nil {
		head = node
	} else {
		curr := head

		for curr.next != nil {
			curr = curr.next
		}

		curr.next = node
	}

	return head
}

func countNodes(head *Node) int {
	count := 0

	for head != nil {
		count++
		head = head.next
	}

	return count
}

func getMedian(head *Node, size int) float64 {
	arr := make([]int, size)

	for i := 0; head != nil; i++ {
		arr[i] = head.value
		head = head.next
	}

	sort.Ints(arr)

	if size%2 == 0 {
		return float64(arr[size/2-1]+arr[size/2]) / 2
	} else {
		return float64(arr[size/2])
	}
}

func main() {
	var head *Node

	head = addNode(head, 5)
	head = addNode(head, 1)
	head = addNode(head, 3)
	head = addNode(head, 2)
	head = addNode(head, 4)

	size := countNodes(head)
	median := getMedian(head, size)

	fmt.Println("The median is:", median)
}
973 chars
73 lines

In this code, we first define a linked list and two helper functions - addNode and countNodes. addNode is used to add a new node to the linked list, and countNodes is used to count the number of nodes in the linked list.

We then define the getMedian function which calculates the median by first creating an array of all the values in the linked list, sorting the array, and then calculating the median based on the number of nodes.

Finally, we create a test case with a linked list containing 5 nodes and calculate the median. The output is The median is: 3, which is the correct median for this test case.

similar go code snippets

find the median of all nodes in a linked list in go

find the length of a linked list in go

remove a node from the end of a linked list in go

add a node to the beginning of a linked list in go

remove a node from the beginning of a linked list in go

remove a node from the middle of a linked list in go

create a linked list in go

find the last node in a linked list in go

find the first node in a linked list in go

add a node to the end of a linked list in go

related categories