DEV Community

Cover image for Merge two Sorted Linked List in Go
Mohammad Aziz
Mohammad Aziz

Posted on

Merge two Sorted Linked List in Go

#go

A linked list is a linear way to structure the data so that any arbitrary number of data we can store. That means it's flexible on the memory limitation as compare to arrays.

What do I mean by linear?

A linear data structure is where I can go to only one other element from the current one.

One supposes you already have two linked lists and they are already sorted how do you merge it effectively? What I mean by being effective is how can you swap the node in memory of a list without having to manage an extra dummy node?

Show me some code

Let go through each method one by one.

The first two are simple. The Print is to help print all the values in the linked list and Push will add value at the tail of the linked list.

The Output is 3 5 7 11

As promised since both linked lists are sorted then the expected output is very simple to guess.

var result *Node = nil

The result value is what we will be returning to the caller. At the start, there isn't any result so that's why keeping it nil.

moveNode(dest **Node, source **Node)

The dest and source are pointers to a struct pointer. The value of dest will be a nil value because of lastPtrRef = &((*lastPtrRef).next). In this function what happening is, we're setting the last value to the next node of the sorted list while doing that we're also updating the result variable. We're also clearing the value which should be removed from the top of the sorted list.

Reference

  1. https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/

Discussion (0)