数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法学研究JavaScript：如何查找链表的中间元素？
对于给定的链表，编写一个JavaScript程序来查找其中间元素。在这里，链表是一种线性数据结构。
如果链表中元素个数为偶数，则会有两个中间节点。在这种情况下，中间元素将是这两个元素中的后一个元素。
示例场景
Input: linked_list = 1->2->3->4->5->6-> null Output: middle_element = 4
使用迭代
遍历整个列表并计算节点数。现在，遍历节点直到count/2，并返回count/2，即中间元素。
示例
下面的JavaScript程序演示了如何查找链表的中间元素。
<html>
<head>
<title>Middle Element of Linked List</title>
</head>
<body>
<script>
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
}
// to add a new node
push(new_data) {
let new_node = new Node(new_data);
if (!this.head) {
this.head = new_node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = new_node;
}
}
// counting nodes
getCount() {
let count = 0;
let current = this.head;
while (current) {
count++;
current = current.next;
}
return count;
}
// for getting middle node
printMiddle() {
let count = this.getCount();
let mid = Math.floor(count / 2);
let current = this.head;
for (let i = 0; i < mid; i++) {
current = current.next;
}
return current.data;
}
}
const linkedlist = new LinkedList();
linkedlist.push('Node 12');
linkedlist.push('Node 24');
linkedlist.push('Node 48');
linkedlist.push('Node 95');
linkedlist.push('Node 56');
document.write('The middle element is: ' + linkedlist.printMiddle());
</script>
</body>
</html>
运行此代码后，将产生以下输出：
The middle element is: Node 48
使用双指针
使用两个指针（慢指针和快指针）遍历链表。慢指针一次移动一个节点，快指针一次移动两个节点，直到快指针指向null。当快指针到达末尾时，慢指针将指向中间元素。
示例
在下面的示例中，我们将使用双指针方法在JavaScript中查找链表的中间元素。
<html>
<head>
<title>Middle Element of Linked List</title>
</head>
<body>
<script>
// Defining the head pointer
var head;
/* Linked list node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/* Function to print middle
of linked list */
function printMiddle(){
var slow_ptr = head;
var fast_ptr = head;
if (head != null){
while (fast_ptr != null &&
fast_ptr.next != null){
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
document.write(
"The middle element is [" + slow_ptr.data + "] <br/><br/>"
);
}
}
/* Inserts a new Node at front of the list. */
function push(new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*
* This function prints contents of linked
list starting from the given node
*/
function printList() {
var tnode = head;
while (tnode != null) {
document.write(tnode.data + "->");
tnode = tnode.next;
}
document.write("NULL<br/>");
}
for (i = 4; i > 0; --i) {
push(i);
printList();
printMiddle();
}
</script>
</body>
</html>
它将产生以下输出：
5->NULL The middle element is [5] 4->5->NULL The middle element is [5] 3->4->5->NULL The middle element is [4] 2->3->4->5->NULL The middle element is [4]
更新于：2024年9月30日
1K+ 次浏览
广告