CodeX
Published in

CodeX

Golang with Leetcode: Remove Nth Node From End of List

Leetcode Problem #19: Remove Nth Node From End of List in Go

src: The Gopher Gala is the first worldwide Go hackathon — The Go Programming Language

Motivation

Recently, I decided that I wanted to prep for interviews, coding competitions, and learn a new programming language. To kill all of these birds with one stone, I decided to practice Leetcode problems daily with Golang. Solving algorithm problems in a language you aren’t familiar with forces you to think about the problem that actually needs to be solved, which helps you become a better developer. Of course, there are the initial hiccups with getting the correct syntax, but the most important thing is being able to solve problems regardless of tooling.

Soon after this journey began, I noticed that there isn’t nearly as much support for Leetcode problems in Golang as there is C++, Python, or Java. Given the history of those languages, its not surprising that a modern language like Go doesn’t have the same level of support. However, this article will be the first in a series of posts where I provide solutions to Leetcode problems in Golang.

DISCLAIMER: As mentioned before, I am still learning Go. If anyone has any recommendations to make my code more idiomatic, please provide in the comments

Remove Nth Node From End of List

Difficulty: Medium

Acceptance Rate: 38.0%

Problem Breakdown

At a high level overview, this problem wants you to remove an element from a linked list. There are key fundamentals to how linked lists work, which are that their traversal time and access time are both O(n). Linked lists do not have the same indexing capabilities as arrays do; these capabilities allow for arrays to have constant, or O(1), access time. Before you can access a linked list element, you must traverse the list to that element.

Removing an element from a linked list is usually where people get stuck due to confusion around pointers. We are given a singly linked list, meaning that nodes can only point forward, not backwards. This will mean we only have to change one node pointer. In addition, Go utilizes a garbage collector for memory management so we will not need to perform manual deallocation as we would in a language like C++. When we remove the nth node, we will simply change the pointer at the nth-1 node to point to the nth+1 node.

The trick to this problem is that it wants you to remove n positions from the end of the list. As mentioned before, we do not have indexing capabilities which would allow us to start from any position in the list. So there are 2 strategies we can deploy: we can maintain 2 pointers separated by n distance from one another, or we can traverse the list and get the count of elements in the list. After we get the count of elements, we can subtract n and this will give us the position we are needing to have removed. After that, we simply traverse the list and remove the node located at the derived position. The solution provided is the second potential solution I provided above.

There are a few edge cases to watch out for:

  • Linked list size is 1 and remove position is 1 will need to result in an empty list
  • If nodeCount and n are equal, then you are being asked to remove the first element in the list, and we will simply need to point the head pointer to the next node

Solution

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
tempNode := head
nodeCount := 0
for tempNode != nil {
nodeCount++
tempNode = tempNode.Next
}

removePosition := nodeCount - n

if n != 0 {
if removePosition > 0 {
tempNode = head
for i := 0; i < removePosition-1; i++{
tempNode = tempNode.Next
}
tempNode.Next = tempNode.Next.Next
} else if nodeCount == 1 && n == 1 {
head = nil
} else if nodeCount == n {
head = head.Next
}
}
return head
}

Performance

--

--

--

Everything connected with Tech & Code. Follow to join our 900K+ monthly readers

Recommended from Medium

How to optimize PowerApps performance

OMNET++ VS NS3

Hosting multiple web projects web developer

“We have no choice but to…” is a weak word choice sometimes made by new software managers.

Fomo Apes V2

Cinematography in Unity — Introduction to Timeline

Pry - Getting to The “True Knowledge”

Getting Started with Kivy: How to Code Desktop and Mobile Apps with Python

Screen Shot 2022-03-09 at 2.27.30 PM.png

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alec Garza

Alec Garza

Software Developer

More from Medium

Leetcode with Golang: Integer to Roman Conversion

Details of Go JSON serialization of []byte type

json: cannot unmarshal object into a Go struct field

Golang: How To Implement Concurrency With Goroutines and Channels