[Sword means Offer] 3. Print linked list from end to end

Title description

Enter a linked list and return an ArrayList from the end of the list.

Analysis

To understand the data structure of linked lists:

The val property stores the current value and the next property stores a reference to the next node.

To traverse the linked list is to find the next node of the current node continuously. When the next node is null, it means that it is the last node and stop traversing.

Finally, don’t forget to traverse the linked list from end to end, and don’t forget to flip your results.

Code

/*function ListNode(x){
 this.val = x;
 this.next = null;
 }*/
 function printListFromTailToHead(head)
 {
 const result = [];
 let temp = head;
 while(temp){
 result.push(temp.val);
 temp = temp.next;
 }
 return result.reverse();
 }

Expand

Linked list definition: use a set of arbitrarily stored cells to store data elements of linear tables.

An object stores its own value and the address of the next element.

It takes traversal to query elements, and the query is slow.

Insert elements only need to be disconnected and reassigned. Insert quickly.

function LinkList(){
function node(element){
this.value = element;
this.next = null;
}
let length = 0;
let head = null;
}
LinkList.prototype = {
//Append
append:function(element){
var node = new node(element);
var temp = this.head;
if(this.head){
//Traversal to Find End of Linked List
while(temp.next){
temp = temp.next;
}
temp.next = node;
}else{
this.head = node;
}
this.length++;
},
//insert
insert:function(element,index){
if(index <= this.length && index>0){
var node = new node(element);
var currentIndex = 0;
var currentNode = this.head;
var preNode = null;
if (currentIndex === 0) {
node.next = currentNode;
this.head = node;
return;
}
while(currentIndex<index){
preNode = currentNode;
currentNode = currentNode.next;
currentIndex++;
}
preNode.next = node;
node.next = currentNode;
this.length++;
}
}
}

Linked list inversion

The initial linked list head is taken as a reference point

Move the next element to the header

Until the next element is empty

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
 /**
 * @param {ListNode} head
 * @return {ListNode}
 */
 var reverseList = function (head) {
 let currentNode = null;
 let headNode = head;
 while (head && head.next) {
 //Remove the current node from the linked list
 currentNode = head.next;
 head.next = currentNode.next;
 //Move the removed node to the head
 currentNode.next = headNode;
 headNode = currentNode;
 }
 return headNode;
 };