Блог

Мой вопрос касается связанного списка и указателей, я знаю linkedlist и как он работает, но моя проблема в том, что:

У меня есть этот пример нечетно-четного связанного списка :

 // 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));
 

В результате будет :

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

поэтому мой вопрос таков :
что здесь произошло, когда мы добавили :

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

Я знаю odd , что var сейчас будет : [1,2,3,4,5,6]
и в то же время even будет : [2,3,4,5,6,7]

проблема в следующем : odd и even после того, как цикл будет равен:

    odd = [7] 
   even = null
 

и в последней строке, когда мы добавим : odd.next = evenHead
это среднее odd значение будет равно odd=[7,1,2,3,4,5,6,7]
но когда я вернусь odd , будет что-то вроде этого: odd=[1,3,5,2,4,6,7]

и в то же время, когда я вернусь head , будет равен odd тому же результату : head=[1,3,5,2,4,6,7]

почему odd var влияет на head и even var влияет на evenHead ?

Надеюсь, вы понимаете, что я имею в виду:

простое резюме, если вы не понимаете приведенное выше объяснение

 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)); 

odd.next = evenHead это означает odd , что будет равно odd=[7,1,2,3,4,5,6,7] , но когда я вернусь odd , это будет что-то вроде этого: odd=[1,3,5,2,4,6,7]

Причина в том, что цикл переписал список. Перед выполнением цикла список, начинающийся с head :

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

Но цикл перенаправляет все эти «стрелки», так что после цикла ссылки выглядят следующим образом:

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

И когда последнее задание будет выполнено, мы получим окончательный результат:

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

Поэтому , если затем вы посмотрите odd , вы найдете следующую последовательность списков: [7, 2, 4, 6]. Если бы цель состояла в том, чтобы сначала получить все нечетные значения, а затем все четные значения, то операторы после цикла должны измениться с этого:

 odd.next = evenHead
return head;  
 

к этому:

 even.next = head
return evenHead;  
 

Они будут выполнены, когда состояние будет следующим (я повторяю):

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

Но с этими заключительными заявлениями мы получаем следующее:

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

…а затем evenHead будет возвращено, так что последовательность будет [2, 4, 6, 1, 3, 5, 7].