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