Find the nth Node from the End of a Linked List in Go

Program Code

package main

import "fmt"

// ListNode defines a node in a singly linked list
type ListNode struct {
    Val  int
    Next *ListNode
}

// findNthFromEnd finds the nth node from the end of a linked list
func findNthFromEnd(head *ListNode, n int) *ListNode {
    // Initialize two pointers
    first := head
    second := head

    // Move the first pointer n steps ahead
    for i := 0; i < n; i++ { if first == nil { return nil // n is greater than the length of the list } first = first.Next } // Move both pointers until the first pointer reaches the end while first != nil { first = first.Next second = second.Next } return second } // Helper function to print the linked list func printList(head *ListNode) { for head != nil { fmt.Print(head.Val, " ") head = head.Next } fmt.Println() } // Main function to test the findNthFromEnd function func main() { // Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
    head := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, nil}}}}}

    fmt.Print("Original List: ")
    printList(head)

    n := 2
    nthNode := findNthFromEnd(head, n)

    if nthNode != nil {
        fmt.Printf("The %dth node from the end is: %d\n", n, nthNode.Val)
    } else {
        fmt.Println("The position is greater than the length of the list.")
    }
}
    

Explanation

The Go program is designed to find the nth node from the end of a singly linked list. Here is a detailed explanation of the program structure:

1. ListNode Definition

The ListNode struct defines a node in a singly linked list, which contains a value (Val) and a pointer to the next node (Next).

2. findNthFromEnd Function

The findNthFromEnd function locates the nth node from the end of the linked list:

• Initializes two pointers, first and second, both pointing to the head of the list.
• Moves the first pointer n steps ahead. If first becomes nil before taking n steps, it means n is greater than the length of the list, and the function returns nil.
• Then, it moves both pointers (first and second) together until the first pointer reaches the end of the list. At this point, the second pointer points to the nth node from the end.
• Returns the second pointer, which now points to the nth node from the end.

3. printList Function

The printList function is a helper to print the values of the linked list for demonstration purposes.

4. Main Function

The main function demonstrates the usage of the findNthFromEnd function:

• Creates a linked list: 1 -> 2 -> 3 -> 4 -> 5.
• Prints the original list.
• Finds the 2nd node from the end using findNthFromEnd and prints its value.
• If findNthFromEnd returns nil, it indicates that n is greater than the length of the list.