我正试图将另一个链表添加到空链表。L1是一个空链表,l2有3个元素。
///代码片段current = l1.head;
if (current === null){
current = l2.head;
}
当我运行这个并打印l1时,我得到undefined
但是当我把代码改成:
current = l1.head;
if (current === null){
l1.head = l2.head;
}
输出l2的元素,最后输出一个undefined。这是什么原因呢?
添加我使用的链表类的代码片段:
// Creating a class for node that will be the building block for our linked list.
// Each element in the linked list will be stored in a node.
class Node{
constructor(data = null, next = null){ // The node will have two attributes: the data it has and the pointer to next node
this.data = data;
this.next = next;
}
}
// Creating the linked list class
class linkedlist {
constructor(){ // The main attributes of the linked list are the head and its size.
this.head = null;
this.size = 0;
}
// Method to insert data at the start of the linked list
insert(data){
this.head = new Node(data, this.head); // Assigning the new data to the head of the linked list. And whatever is in the head is assigned to the next parameter.
this.size++; // Increase the size to keep track.
}
// Method to insert data at end
insertEnd(data){
let current = this.head; // Use current to traverse through the linked list. setting it to head.
if(current === null){
this.head = new Node(data);
}
else{
while(current.next !== null){ // Using a while loop to traverse through the linked list.
current = current.next; // Going all the way to the end. when the next becomes null we will exit the while loop indicating we reached the end.
}
current.next = new Node(data); // Now that we reached the end we assign the next to the new node.
}
this.size++; // Increase size to keep track.
}
// Method to insert data at a particular index
insertAt(index, data){
if(this.size < index){ // Cheking if the index requested is in bounds
return console.log('Out of bounds');
}
else{
var current = this.head; // Using current to traverse the linked list and initializing it to the head.
var previous; // Initializing another variable previous.
let i = 0;
while(i < index){ // Using a while loop to traverse to the index.
previous = current; // Assigning current to previous so that we can have a record of previous and next element in the linked list.
i++;
current = current.next; // Traversing the linked list.
}
// While loop will exit once we reach the node just before the index where we want insert the data.
const node = new Node(data); // Creating a new node with the new data.
node.next = current; // So the current node will be assigned as the next since it is at the index we want to insert the data.
previous.next = node; // The previous which has the data of the node before the index will get the new node as its next.
this.size++; // Increase size to keep track.
}
}
// Method to remove element from an index
removeat(index){
let count = 0, previous; // Initializing some variables.
let current = this.head; // setting current to head to be able to traverse the linked list.
if (index > this.size){ // Checking if the index is out of bounds
console.log("Index out of bounds");
}
else{
while(count < index){ // Using while loop to traverse through the linked list till the index
previous = current; // Assigning current node to previous to keep track of consecutive nodes.
current = current.next;
count++;
}
// While loop exits when we reach the index where we want to remove the data from.
previous.next = current.next; // To remove the node at the index assign the next of the previous node to the next of the current node. Thus removing the pointer to the current node.
}
this.size--; // Decrementing to keep track of size.
}
// Method to clear all the elements from the linked list
clear(){
this.head = null; // Assigning the head to null automatically clears all the data in the linked list cos it will have no reference to any elements in the list anymore.
this.size = 0; // Updating the size of the linked list.
}
// Method to display all the data in the linked list
show(){
let current = this.head; // Initializing current to head to traverse through the linked list.
while(current != null){ // While current not null.
console.log(current.data); // Printing the data to the console.
current = current.next;
}
}
}
let l1 = new linkedlist();
let l2 = new linkedlist();
l2.insertEnd(1);
l2.insertEnd(3);
l2.insertEnd(4);
合并两个链表的简单函数。
var mergeTwoLists = function(l1, l2) {
current = l1.head;
if (current === null){
current = l2.head;
}
return l1;
};
我期望的是l1表现在指向l2表的头。但是,当我输出l1时,我仍然得到null。
第一个代码片段不起作用,因为列表只能在设置其head
引用或设置其节点的next
引用之一时获得额外的节点。你的第一个代码没有做这些,它只是设置了一个局部变量current
,它不影响列表。
current
先前被设置为l1.head
的事实并不影响对current
的另一个赋值。它是一个单独的变量;它不是列表的head
属性。
第二个代码片段运行良好,如下所示。我还完成了合并函数,因为它可以应用与insertEnd
相同的原理。我删除了您的问题不需要的所有其他方法:
class Node{
constructor(data = null, next = null) {
this.data = data;
this.next = next;
}
}
class linkedlist {
constructor() {
this.head = null;
this.size = 0;
}
insertEnd(data) {
let current = this.head;
if (current === null) {
this.head = new Node(data);
} else {
while (current.next !== null) {
current = current.next;
}
current.next = new Node(data);
}
this.size++;
}
show() {
let current = this.head;
while (current != null) {
console.log(current.data);
current = current.next;
}
}
}
function mergeTwoLists(l1, l2) {
current = l1.head;
if (current === null){
l1.head = l2.head;
} else { // Same principle as in insertEnd:
while (current.next !== null) {
current = current.next;
}
current.next = l2.head;
}
l1.size += l2.size // Don't forget!
return l1;
};
let l1 = new linkedlist();
let l2 = new linkedlist();
l2.insertEnd(1);
l2.insertEnd(3);
l2.insertEnd(4);
console.log("list 1:");
l1.show();
console.log("------");
console.log("list 2:");
l2.show();
console.log("------");
mergeTwoLists(l1, l2);
console.log("merge of list 1 and list 2:");
l1.show();
console.log("------");
// Another test
let l3 = new linkedlist();
l3.insertEnd(13);
console.log("list 3:");
l3.show();
console.log("------");
mergeTwoLists(l1, 42);
console.log("merge of list 1 and list 3:");
l1.show();