{"type":"challenge","category":{"id":6,"name":"linked lists","description":"A collection of nodes that are connected by links or pointers.","created_at":"2018-08-10T23:55:13.000Z","updated_at":"2020-05-29T00:15:07.445Z","slug":"linked-lists","challenges_count":13,"sequence":1,"section_id":7},"challenge":{"difficulty":6,"created_at":"2019-03-17T18:36:43.132Z","updated_at":"2020-06-17T01:39:51.444Z","slug":"reverse-a-linked-list","title":"Reverse a Linked List","question":"You're sent a `linked list` of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows: ```js // 17 -> 2 -> 21 -> 6 -> 42 -> 10 ``` Write an algorithm for a method `reverseList` that takes in a `head` node as a parameter, and reverses the linked list. It should be capable of reversing a list of any length. You may use the example `linked list` for testing purposes. Your method will be called as such: ```js class LinkedListNode { constructor(val, next = null) { this.val = val; this.next = next; } } l1 = new LinkedListNode(1); l1.next = new LinkedListNode(2); reverseList(l1); ```","id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":60,"has_trace":true,"kind":"algorithms","video":"","locked":false,"environment":"linked lists","initialCode":"```js function reverseList(head) { // Fill in this method return head; } ```","language_content_id":83,"languages_supported":[22,29,34,38,26],"solutionCode":"```js // iterative function reverseList(head) { if (head.length < 2) { return; } let newHead = null; while (head != null) { let nextNode = head.next; head.next = newHead; newHead = head; head = nextNode; } return newHead; } // recursive function reverseList(head) { if (!head || !head.next) { return head; } let rest = reverseList(head.next); head.next.next = head; delete head.next; return rest; } ```","tests":[{"id":177,"text":"Reversing linked list `3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10` should return `10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3`","test_string":"var reversed = reverseList(list1); assert.deepEqual(listToString(reversed), '10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3');","language_content_id":83,"screen_id":null,"created_at":"2020-06-06T21:32:57.405Z","updated_at":"2020-06-06T21:32:57.405Z"}]},"completed":null,"language":null,"nextArr":["Challenge","linked-list-to-binary-search-tree"],"screens":[{"id":428,"kind":"question","options":[],"content":"You're sent a `linked list` of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows: ```js // 17 -> 2 -> 21 -> 6 -> 42 -> 10 ``` Write an algorithm for a method `reverseList` that takes in a `head` node as a parameter, and reverses the linked list. It should be capable of reversing a list of any length. You may use the example `linked list` for testing purposes. Your method will be called as such: ```js class LinkedListNode { constructor(val, next = null) { this.val = val; this.next = next; } } l1 = new LinkedListNode(1); l1.next = new LinkedListNode(2); reverseList(l1); ```","code":"","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":1,"title":"Description","slug":"description","created_at":"2020-05-29T00:13:39.889Z","updated_at":"2020-06-23T15:57:06.455Z"},{"id":429,"kind":"info screen","options":[],"content":"Seems pretty easy, right? To reverse an entire linked list, simply reverse every pointer. If `1` is pointing at `2`, flip it so `2` should point to `1`. ","code":"```js // 17 -> 2 -> 21 -> 6 -> 42 -> 10 // becomes // 17 <- 2 <- 21 <- 6 <- 42 <- 10 ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":2,"title":"Step Two","slug":"info-screen-D_xMPcuEvEA","created_at":"2020-05-29T00:13:39.996Z","updated_at":"2020-05-29T00:13:39.996Z"},{"id":430,"kind":"info screen","options":[],"content":" The actual reversal method is actually pretty straightforward, but be aware that it takes some time to reason out. It's easy to get lost, so make sure you draw lots of diagrams. As this is a problem (reversing an entire linked list) that can be broken up into sub-problems (reverse the pointer between two nodes), it seems like a good opportunity to use recursion. ","code":"","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":3,"title":"Step Three","slug":"info-screen-cnMkoAkpSME","created_at":"2020-05-29T00:13:40.103Z","updated_at":"2020-05-29T00:13:40.103Z"},{"id":431,"kind":"info screen","options":[],"content":"There are many ways to do the actual reversal, and we'll cover both an **iterative** and **recursive** approach, but the general methodology is as follows: 1. Begin by creating 3 pointers: `newHead`, `head` and `nextNode`. 1. `newHead` and `nextNode` are initialized to `null`. 2. `head` starts off pointing to the head of the linked list. 2. Iterate (or recursively do) through the following process until `head` is `null`. This means that the end of the list has been reached: _Note: KEEP GOING DOWN FOR A STEP BY STEP WALKTHROUGH OF THE ITERATIONS_ ","code":"```js class LinkedListNode { constructor(val, next = null) { this.val = val; this.next = next; } } l1 = new LinkedListNode(1); l2 = new LinkedListNode(2); l1.next = l2; // we start at head let head = l1; let newHead = null; while (head != null) { // store the node to the right to reuse later let nextNode = head.next; // set the current node's next to point backwards head.next = newHead; // store the current node, to be used as the new next later newHead = head; // the previously right-side node is now processed head = nextNode; } console.log(l2); ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":4,"title":"Step Four","slug":"info-screen-FoLSO42QGow","created_at":"2020-05-29T00:13:40.210Z","updated_at":"2020-05-29T00:13:40.210Z"},{"id":432,"kind":"info screen","options":[],"content":" It's difficult to visualize this chain of events, so let's use comments to visualize it. During the interview, _try not to keep it in your head_. ","code":"","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":5,"title":"Step Five","slug":"info-screen-D91+h_n3ipA","created_at":"2020-05-29T00:13:40.317Z","updated_at":"2020-05-29T00:13:40.317Z"},{"id":433,"kind":"info screen","options":[],"content":"It'll be especially difficult while balancing your nerves and talking to the interviewer. Take advantage of the whiteboard not just to record things, but also to think through potential steps. Let's walk through it step by step and then look at working code. Let's reverse an extremely basic list, like `8 -> null`. The first line is `let nextNode = head.next;`, which will store the node to the right. ","code":"```js nextNode = 4 // 8 -> 4 ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":6,"title":"Step Six","slug":"info-screen-xD+ZAl75cNc","created_at":"2020-05-29T00:13:40.424Z","updated_at":"2020-05-29T00:13:40.424Z"},{"id":434,"kind":"info screen","options":[],"content":" Then we'll do `head.next = newHead;`, which will set the current node's `next` to point backwards. ","code":"```js nextNode = 4 // <- 8, 4 ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":7,"title":"Step Seven","slug":"info-screen-FzmQ_gJZjG4","created_at":"2020-05-29T00:13:40.531Z","updated_at":"2020-05-29T00:13:40.531Z"},{"id":435,"kind":"info screen","options":[],"content":" Now `newHead = head;` will store the current node, to be used as the new next later. ","code":"```js newHead = 8 nextNode = 4 // <- 8, 4 ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":8,"title":"Step Eight","slug":"info-screen-8QFG6vUZaSo","created_at":"2020-05-29T00:13:40.638Z","updated_at":"2020-05-29T00:13:40.638Z"},{"id":436,"kind":"info screen","options":[],"content":" Finally, the previously right-side node is now processed: ","code":"```js newHead = 8 nextNode = 4 // <- 8, 4 ^ current node ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":9,"title":"Step Nine","slug":"info-screen-ksAIrkYD45Q","created_at":"2020-05-29T00:13:40.745Z","updated_at":"2020-05-29T00:13:40.745Z"},{"id":437,"kind":"info screen","options":[],"content":" Now we process the next one with the same steps. `nextNode = head.next;` will store the node to the right. ","code":"```js newHead = 8 nextNode = null // <- 8, 4 ^ current node ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":10,"title":"Step Ten","slug":"info-screen-5ck+0uxQMLw","created_at":"2020-05-29T00:13:40.851Z","updated_at":"2020-05-29T00:13:40.851Z"},{"id":438,"kind":"info screen","options":[],"content":" Again, set the current node's `next` to point backwards with `head.next = newHead;`. Recall that `newHead` is `8`! This is where we make the switch: ","code":"```js newHead = 8 nextNode = null // <- 8 <- 4 ^ current node ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":11,"title":"Step Eleven","slug":"info-screen-Mn2a6qc8DL8","created_at":"2020-05-29T00:13:40.958Z","updated_at":"2020-05-29T00:13:40.958Z"},{"id":439,"kind":"info screen","options":[],"content":" Now let's see this all put together in code, with lots of comments for edification! ","code":"```js class LinkedListNode { constructor(val, next = null) { this.val = val; this.next = next; } } l1 = new LinkedListNode(8); l2 = new LinkedListNode(4); l1.next = l2; // start at head, 8 let head = l1; // example: 8 -> 4 let newHead = null; while (head) { /* FIRST PASS */ // store the node to the right let nextNode = head.next; // nextNode = 4, still 8 -> 4 // set the current node's next to point backwards head.next = newHead; // 8 -> null // store the current node, to be used as the new next later newHead = head; // newHead = 8 // the previously right-side node is now processed head = nextNode; // head = 4 /* SECOND PASS */ // store the node to the right nextNode = head.next; // nextNode = null // set the current node's next to point backwards head.next = newHead; // 4 -> 8 // store the current node as the previous one newHead = head; // the previously right-side node is now processed head = nextNode; } console.log(l2); ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":12,"title":"Step Twelve","slug":"info-screen-J2LLLvawnrQ","created_at":"2020-05-29T00:13:41.064Z","updated_at":"2020-05-29T00:13:41.064Z"},{"id":440,"kind":"info screen","options":[],"content":" Does that all make sense? Be sure to go through the iterative approach a few times. Here's the recursive way to do it. This can also be tricky, especially on first glance, but realize most of the magic happens when it gets to the end. ","code":"```js function reverseList(head) { if (!head || !head.next) { return head; } let rest = reverseList(head.next); head.next.next = head; delete head.next; return rest; } ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":13,"title":"Step Thirteen","slug":"info-screen-BCpal2mYV9A","created_at":"2020-05-29T00:13:41.171Z","updated_at":"2020-05-29T00:13:41.171Z"},{"id":441,"kind":"info screen","options":[],"content":" Let's take an easy example of `8 -> 4` again `let rest = reverseList(head.next);` takes `4` and calls `reverseList` on it. Calling `reverseList` on `4` will have us reach the termination clause because there is no `.next`: ","code":"```js if (!head || !head.next) { return head; } ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":14,"title":"Step Fourteen","slug":"info-screen-nfLYI0hKBg0","created_at":"2020-05-29T00:13:41.279Z","updated_at":"2020-05-29T00:13:41.279Z"},{"id":442,"kind":"info screen","options":[],"content":" We go up the stack back to when `8` was being processed. `rest` now simply points to `4`. Now notice what happens: ","code":"```js // remember, head is 8 - it is being processed // head.next is 4 head.next.next = head; // head.next.next was null since 4 wasn't pointing to anything // but now head.next (4) points to 8 ```","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":15,"title":"Step Fifteen","slug":"info-screen-sC9WBAoJ3Xg","created_at":"2020-05-29T00:13:41.385Z","updated_at":"2020-05-29T00:13:41.385Z"},{"id":443,"kind":"info screen","options":[],"content":" And we return `4` - which is pointing to `8`. And we can simply extrapolate that to longer linked lists! Note that the recursive approach requires more space because we need to maintain our call stack. ","code":"","full_screen":false,"solution":"","lesson_id":null,"challenge_id":"459fbd7b-06b6-4dcb-a511-d455de70c094","sequence":16,"title":"Step Sixteen","slug":"info-screen-egqe+yL7U10","created_at":"2020-05-29T00:13:41.493Z","updated_at":"2020-05-29T00:13:41.493Z"}],"user":null}