Search code examples
javascriptpointerslinked-listjavascript-objects

Linked List Pointers | what's that mean: next is reference and can be viewed as a link or pointer?


My question is about Linked List and Pointers I know linkedlist and how it's work, but my problem is that:

I have this example odd-even linked list :

// This is class node for create nodes
class Node {
    constructor(val, next) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

// this is our function to return odd nodes followed bt even nodes 
// * return the index of node not the value so if node index is 1 and value is 2 
// thats mean odd node not even cuz we don't care about value
// consider that index start from 1 not from 0

const oddEvenLinkedList = function (head) {
    if (!head) return head;
    var odd = head
    var even = head.next 
    var evenHead = even 
    while (odd.next) {
        odd.next = even.next 
        odd = odd.next 
        even.next = odd.next 
        even = even.next 
    }
    odd.next = evenHead
    return head;  
};
// create our linked list
// Node takes two params Node(value, next_node)
const head = new Node(1, 
             new Node(2, 
             new Node(3, 
             new Node(4, 
             new Node(5, 
             new Node(6, 
             new Node(7)))))))

console.log(oddEvenLinkedList(head));

The result will be :

head = [1,3,5,2,4,6,7] // odd numbers followed by even nubmers

so my question is : what's happened here when we added :

    var odd = head
    var even = head.next 
    var evenHead = even 

I know the odd var now will be : [1,2,3,4,5,6] and at the same time even will be : [2,3,4,5,6,7]

the problem is : odd and even after loop will be equals to:

   odd = [7] 
   even = null

and at the last line when we add : odd.next = evenHead that's mean odd will be equal to odd=[7,1,2,3,4,5,6,7] but when I return odd will be something like this: odd=[1,3,5,2,4,6,7]

and at the same time when I return head will be equal to odd the same result : head=[1,3,5,2,4,6,7]

why odd var effects on head and even var effect on evenHead ?

I hope you understand what I mean:

simple summary if you don't understand the above explanation

let head = [1,2,3,4,5] // linked list 1->2->3...etc
let x = main
let z = main

//for example when change x or z :
x.next = null
//or 
z.next = null // or whatever value

// any changes we do in z or x will affect the head, why?

class Node {
    constructor(val, next) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

var oddEvenLinkedList = function (head) {
    if (!head) return head;
    var odd = head 
    var even = head.next 
    var evenHead = even 
    while (odd.next) {
        odd.next = even.next 
        odd = odd.next 
        even.next = odd.next 
        even = even.next 
    }
    odd.next = evenHead
    return head;  
};
const head = new Node(1, new Node(2, new Node(3, new Node(4, new Node(5, new Node(6, new Node(7)))))))

console.log(oddEvenLinkedList(head));


Solution

  • odd.next = evenHead that means odd will be equal to odd=[7,1,2,3,4,5,6,7] but when I return odd it is something like this: odd=[1,3,5,2,4,6,7]

    The reason is that the loop has rewired the list. Before the loop executes, the list, starting from head, is:

     odd
    head         
      ↓
      1→2→3→4→5→6→7
        ↑
     evenHead
       even 
    

    But the loop redirects all those "arrows", so that after the loop, the links are as follows:

    head         odd
      ↓           ↓
      1→→→3→→→5→→→7
        2→→→4→→→6
        ↑       ↑
     evenHead  even
    

    And when the last assignment has been executed, we get the final result:

    head         odd
      ↓           ↓
      1→→→3→→→5→→→7→→→2→→→4→→→6
                      ↑       ↑
                   evenHead  even
    

    So if then you would look at odd, you will find the following list sequence: [7, 2, 4, 6]. If the purpose would have been to first get all odd values and then all even values, then the statements after the loop should change from this:

    odd.next = evenHead
    return head;  
    

    to this:

    even.next = head
    return evenHead;  
    

    They would be executed when the state is as follows (I repeat):

    head         odd
      ↓           ↓
      1→→→3→→→5→→→7
        2→→→4→→→6
        ↑       ↑
     evenHead  even
    

    But with these final statements we get this:

                  head         odd
                    ↓           ↓
        2→→→4→→→6→→→1→→→3→→→5→→→7
        ↑       ↑
     evenHead  even
      
    

    ...and then evenHead would be returned, so the sequence would then be [2, 4, 6, 1, 3, 5, 7].