leetcode/19_remove_nth_node_from_list

19_remove_nth_node_from_list

dz / leetcode / 19_remove_nth_node_from_list

Summary

19. 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.

Node Tree

Nodes

URL
content URL
hyperlink https://leetcode.com/problems/remove-nth-node-from-end-of-list/

intuition
content This problem just looks like a "do you know how to work with linked lists" problem, and I don't really like these kinds of problems, because it's mostly just about getting the details right instead of patterns and big picture thinking which isn't really what I want to be doing in a stressful interview setting? Anyways, this boils down to removing a node from a singly linked list. Linked lists don't keep track of indice positions, so you have to use a loop of some kind that has a counter. Removing a node is a matter of updating the pointer of the previous node to point to the new next node. If the node being removed is the current head, the head is updated and that is returned.
children dummy_pointer, two_pass_similar_to_my_intuition

editorial
content surprisingly, there are two solutions a "two pass" algorithm and a "one pass", with the one pass being the more complex answer. Honestly, these answers are confusing to me, so I'm going to try and understand what they are trying to say better.
children ooh_the_list_is_backwards, backwards_linked_lists_are_difficult, dummy_pointer

ooh_the_list_is_backwards
content oooh, the list is backwards, with the end of the list being the last element. I should have looked at this more closely. oops.
children two_pass_similar_to_my_intuition (if I had read this mroe carefully, I would have come,with something like this)
parents editorial

two_pass_similar_to_my_intuition
parents intuition, ooh_the_list_is_backwards

single_pass
content the single pass algorithm works by maintaining two pointers. The first pointer moves N+1 steps, and the second pointer is set to be the head, which makes them N nodes apart. These are then moved down the list until the first pointer reaches the end, which will then set the second pointer in place.

dummy_pointer
content I did not think to use a dummy pointer, and I don't think I would have thought of it. I don't really use linked lists in reverse order like this.
parents intuition, editorial

backwards_linked_lists_are_difficult
content I've been working with linked list data structures for years now, and this was difficult for me to think about. When the first element is the last element in the linked list, it adds a bit of a wrinkle to my thought process. I've always need to draw things out for linked lists, so I suppose getting comfortable with this will involve some more careful study.
parents editorial