linked_list_mechanics.md

CASE FOR LENGTH 2 LINKED LIST

item0      
next  ------> item1
val=2         next -------> null
              val=5

            item0       
null <----- next         item1
            val=2        next ------> null
                         val=5

            item0       
null <----- next         item1
            val=2 <----- next 
                         val=5

function  reverseList(node) {
        //what if 0 node in list
        if (node == null) {
            return null;
        }
        //what if 1 node in list
        if (node.next == null) {
            return node;
        }
        //reverse recursively and link second.next to first 
        const secondElem = node.next;
        node.next = null;
        const reverseRest = reverseList(secondElem);
        secondElem.next = node;
        return reverseRest; 

CASE FOR LENGTH 3+ LINKED LIST

RECURSION (on item0)

item0      
next  ------> item1
val=2         next -------> item2
              val=5         next ----------> null
                            val=50

node = item0
secondElem = item1
item0.next = null

           item0      
null<----- next          item1
           val=2         next -------> item2
                         val=5         next ----------> null
                                       val=50

RECURSION (on item1)

item1
next -------> item2
val=5         next ----------> null
              val=50

node = item1
secondElem = item2
item1.next = null

           item1
null <---- next          item2
           val=5         next ----------> null
                         val=50

RECURSION (on item2)

item2
next ----------> null
val=50

B is satisfied

returns item2

RECURSION (on item1)

reverseRest = item2
item2.next = item1

           item1
null <---- next          item2
           val=5 <------ next 
                         val=50

returns item1

RECURSION (on item0)

reverseRest = item1
item1.next = item0

             item0      
null <-----  next          item1
             val=2 <------ next <------- item2
                           val=5         next 
                                         val=50

returns item2

function  reverseList(node) {
        // what if 0 node in list
        if (node == null) { // A
            return null;
        }
        // what if 1 node in list
        if (node.next == null) { // B
            return node;
        }
        //reverse recursively and link second.next to first 
        const secondElem = node.next; // C
        node.next = null; // D
        const reverseRest = reverseList(secondElem); // E
        secondElem.next = node; // F
        return reverseRest; // G