Discussion on: Linked Lists: What They Are and How They Compare to Arrays

View post

I was just browsing through your posts and saw this and the reversing array ones and thought to myself reversing a linked list would make an interesting recursion example.

Usually when seasoned devs introduce recursion to a newcomer dev, we use an example something like

function recurseMe(prettyPlease) {
  do something
  return early if one of the final conditions reached
  return recurseMe(prettyPrettyPlease)
}

In this case though, it will be a bit different, as in

function reverseLink(node) {
  if (!node.next) return node; // old tail reached, return as new head
  reverseLink(node.next); // recurse first
  node.next.next = node; // then reverse link
}
// then to actually reverse a list
const newTail = oldHead;
const newHead = reverseLink(oldHead);