[Go] Linked List - Remove Nth Node From End of List

 

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

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

 

Follow up: Could you do this in one pass?

 

   Hide Hint #1  

Maintain two pointers and update one with a delay of n steps.

Mycode

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	count := 0
	h := head
	for h != nil {
		h = h.Next
		count++
	}

	index := count - n

	h = head
	prev := h
	if index == 0 {
		if h.Next == nil {
			return nil
		} else if h.Next.Next != nil {
			h.Val = h.Next.Val
			h.Next = h.Next.Next
			return head
		} else if h.Next != nil {
			h.Val = h.Next.Val
			h.Next = nil
			return head
		}

	}
	for index != 0 {
		prev = h
		h = h.Next
		index--
	}

	prev.Next = h.Next

	return head
}

sample 0 ms submission & sample 2300 KB submission

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    p1, p2 := head, head
    for n > 0 {
        p2 = p2.Next
        n--
    }
    
    if p2 == nil {
        return p1.Next
    }
    
    for p2.Next != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    
    p1.Next = p1.Next.Next
    return head
}

• I don't know this logic.
• p1, p2 will have head address.
• p2 will move n times.
• p1 will have gap as many as end - n

sample 1 ms submission

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getLengthOfLinkedList(head)
    // fmt.Printf("length: %d\n", length)
    toRemove := length - n 
    // fmt.Printf("toRemove: %d\n", toRemove)
    if toRemove == 0 {
        return head.Next
    }
    tmp := head
    tmpHead := tmp
    for i := 0; i < length && tmp != nil; i++ {
        if toRemove-1 == i {
            // fmt.Printf("to remove: %d, ", tmp.Val)
            remove := tmp.Next
            tmp.Next = remove.Next
        } else {
            // fmt.Printf("next: %d, ", tmp.Val)
            tmp = tmp.Next
        }
    }
    return tmpHead
}

func getLengthOfLinkedList(h *ListNode) int {
    tmp, count := h, 0
    for (tmp != nil) {
        count++
        tmp = tmp.Next
    }
    return count
}

sample 2 ms submission

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    slow, fast, count := head, head.Next, 1
    if fast != nil {
        for fast != nil {
            fast = fast.Next
            count ++
        }
    }
    
    fast = head.Next
    
    diff := count - n
    if diff == 0 {
        return head.Next
    }
    for i:=1; i<diff;i++{
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = fast.Next
    
    return head
}

sample 3 ms submission & sample 2100 KB submission

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    start := &ListNode{}
    start.Next = head
    fast, slow := start, start
    
    for i := 0; i < n; i++ {
        fast = fast.Next
    }

    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    
    slow.Next = slow.Next.Next
    
    return start.Next
}

sample 4 ms submission

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	zeroNode := ListNode{
		Val:  0,
		Next: head,
	}

	slow := &zeroNode
	fast := &zeroNode
	for n > 0 && fast.Next != nil {
		fast = fast.Next
        n--
	}

	for fast.Next != nil {
		slow = slow.Next
		fast = fast.Next
	}

	slow.Next = slow.Next.Next

	return zeroNode.Next
}

sample 5 ms submission & sample 2200 KB submission

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    first := head
    for i:=0; i<n; i++ {
        first = first.Next
    }
    second := dummy
    for first != nil {
        second = second.Next
        first = first.Next
    }
    second.Next = second.Next.Next
    return dummy.Next
}