Remove Nth Node From End of List


Given a linked list, remove the n-th node from the end of list and return its head.


Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.


Given n will always be valid.

Follow up:

Could you do this in one pass?


The below solution uses two pointers and does the removal in a single pass. Algorithms is to,

Find the nth node from start, start second pointer from there until head reaches end.

now the second pointer will have hold of the node to delete, delete it and return node.

 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dumbHead := &ListNode{Val : 0, Next : head}
    for n>0 {
        head = head.Next
    prev := dumbHead
    for head!= nil {
        head = head.Next
        prev = prev.Next
    prev.Next = prev.Next.Next
    return dumbHead.Next