Day 4
LeetCode 206. Reverse Linked List
Two Pointer Solution --> O(n) time (while loop)
// @param {ListNode} head // @return {ListNode} var reverseList = function (head) { let [prev, curr, next] = [null, head, null]; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; };
- I'll use
[1,2,3,4,5]
as an example for our linked list. head
provides us the reference to the very beginning element of our linked list- Declare
prev
as null,curr
ashead
, andnext
asnull
. - We will keep executing until we reach the end of the linked list (when we end up at null)
- Declare
- We set
next
equal tocurr.next
, which would be 2. - Set
curr.next
equal toprev
, which starts as null. - Now set
prev
equal tocurr
, which is currently 1. - Set
curr
equal tonext
, which is 2. - What ends up happening is our current element is now 2 and it's
.next
is pointing towards 1.
This problem was conceptually challenging. The idea of list elements changing order while holding references was confusing 😅. Definitely need to study these.