使用 JavaScript 以奇偶节点顺序排列单链表

2025年03月17日 | 阅读 9 分钟

引言

JavaScript 是一种面向对象的编程语言，通常用于增强互联网功能。JavaScript 的一个令人兴奋的操作是处理数据结构，包括链表。在本教程中，我们将探索如何使用 JavaScript 按奇偶节点交替、不寻常和偶数顺序排列链表。这个算法问题需要对链表有扎实的了解，以及正确分割和操作节点的能力。

链表概述

链表是一种类似于节点的线性结构，其中每个节点都指向集合中的下一个节点。单链表以其简洁和动态的性质为特征，使其成为解决此问题的理想解决方案。

问题陈述

给定一个单链表，任务是以这样一种方式排列其节点，使得所有奇数位置的节点都被偶数位置的节点跟随。例如，包含元素 1->2->3->4->5 的链表需要重新排列为 1->3->5->2->4。

方法

要解决此问题，我们可以使用 JavaScript 采用循序渐进的方法。首先，我们需要分割链表，并将奇数或偶数节点分隔到单独的列表中。然后，我们将按所需的顺序合并这些列表。

JavaScript 为处理算法问题提供了一个有效且简洁的平台，包括链表等数据结构的操纵。在本教程中，我们探索了一种以交替的奇偶节点顺序重新排列单链表的方法。理解链表的基础知识并利用 JavaScript 的功能使我们能够将一种有效的方法应用于此问题。随时发展和扩展此代码以满足不同的链表操作需求，或探索 JavaScript 编程领域中更高级的算法。

Arranging Single Linked List in Alternate Odd and Even Nodes Order using JavaScript

方法 1（简单）

在此方法中，我们创建两个栈：奇数栈和偶数栈。我们遍历链表，当遇到奇数位置的偶数节点时，我们将该节点地址压入偶数栈。如果我们遇到偶数位置的奇数节点，则将其地址压入奇数栈。遍历完链表后，我们弹出两个栈顶的节点并交换它们的数据。我们重复此步骤，直到栈变空。

步骤 1

创建奇数和偶数两个栈。这些栈将存储链表中节点的指针。

步骤 2

使用变量 current 从头到尾遍历链表。重复以下操作。

步骤 3

如果当前节点是偶数并且出现在奇数位置，则将该节点地址压入偶数栈。

步骤 4

如果当前节点是奇数并且出现在偶数位置，则将该节点地址压入奇数栈。

（遍历结束）。

步骤 5

两个栈的大小将是相同的。当两个栈都不为空时，交换两个栈顶的节点。然后从各自的栈中弹出两个节点。

步骤 6

链表现已重新排列。

停止

实施

<script> 
// Javascript program to rearrange nodes as alternate odd even nodes in a Singly Linked List class node 
class Node 
{ constructor () 
{ 
this.data = 0; 
this.next = null; 
} 
} 
// A utility function to print 
// linked list 
function print list(node) 
{ 
while (node != null) 
{ 
document.write(node.data + " "); 
node = node. next; 
} 
document.write(); 
} 
//Function to create newNode 
// in a linked list 
function newNode(key) 
{ 
var temp = new Node(); 
temp.data = key; 
temp.next = null; 
return temp; 
} 
//Function to insert at the beginning 
function inserting(head, val) 
{ 
var temp = newNode(val); 
temp.next = head; 
head = temp; 
return head; 
} 
//Function to rearrange the 
// odd and even nodes 
function rearrangeOddEven(head) 
{ 
var odd = []; 
var even = []; 
var i = 1; 
while (head != null) 
{ 
if (head.data % 2 != 0 && 
i % 2 == 0) 
{ 
// Odd Value in Even Position 
// Add a pointer to the current node 
// in odd stack 
odd.push(head); 
} 
else if (head.data % 2 == 0 && 
i % 2 != 0) 
{ 
// Even Value in Odd Position 
// Add a pointer to the current node 
// in even stack 
even.push(head); 
} 
head = head.next; 
i++; 
} 
while (odd.length > 0 && 
even. length > 0) 
{ 
// Swap Data at the top of 
// two stacks 
var k = odd[odd.length - 1].data; 
odd[odd.length - 1].data = even[even.length - 1].data; 
even[even.length - 1].data = k; 
odd.pop(); 
even.pop(); 
}} 
// Driver code 
var head = newNode(8); 
head = insertBeg(head, 7); 
head = insertBeg(head, 6); 
head = insertBeg(head, 5); 
head = insertBeg(head, 3); 
head = insertBeg(head, 2); 
head = insertBeg(head, 1); 
document.write("Linked List:<br/>"); 
printList(head); 
rearrangeOddEven(head); 
document.write("<br/>Linked List after " + 
"Rearranging:<br/>"); 
printList(head); 
// This code is contributed by aashish1995 
</script>

输出

上述代码的输出是

说明

提供的 JavaScript 代码定义了一个链表，并实现了一个函数来根据其位置和值重新排列其节点。链表由一个节点类表示，每个节点都有一个数据字段和一个指向下一个节点的后续指针。printList 指针指向链表的元素。

newNode 函数创建一个具有唯一且重要值的新节点。insert 函数将新节点插入链表的前面。

主要逻辑包含在 rearrangeOddEven 函数中，该函数遍历链表，将奇数值放到偶数位置或偶数值放到奇数位置到单独的栈（普通和偶数）中。然后，它交换两个栈中对应节点的数值。

驱动代码创建链表，并在重新排列奇偶位置的元素后打印链表。重新排列是通过交换值来实现的，从而得到一个修改后的链表。

方法 2（高效）

将链表中的奇数和偶数值分隔开。完成此操作后，所有奇数将连续出现，然后是所有偶数。
将链表分割成奇数列表和偶数列表。
将偶数列表与奇数列表合并。
REARRANGE( HEAD)

1. 步骤 1

使用 NODE TEMP 遍历链表。

如果 TEMP 是奇数

将 TEMP 添加到链表的前面。

（IF 结束）

（遍历结束）

步骤 2

将 TEMP 设置为链表的交替细节。

步骤 3

将 PREV_TEMP 设置为链表的第一个元素。

步骤 4

遍历节点 TEMP 的操作是一个很好的

节点尚未遇到。

= TEMP, TEMP = TEMP- > NEXT

（遍历结束）

步骤 5

将 Even 设置为 TEMP。将 PREV_TEMP- > NEXT 设置为 NULL

步骤 6

I = HEAD, J = Even

步骤 7

重复，直到 I != NULL 且 J != NULL

将 I 和 J 的后续节点存储在 K 和 L 中。

K = I- > NEXT, L = J- > NEXT

I- > NEXT = J, J- > NEXT = K, PTR = J

I = K，J = L。

（循环结束）

步骤 8

如果 I == NULL

PTR- > NEXT = J

（IF 结束）

返回 Head。

步骤 9

End

代码

// JavaScript program to rearrange nodes  
// as alternate odd even nodes in  
// a Singly Linked List  
// Structure node 
class Node  
{ 
    constructor()  
    { 
        this.data = 0; 
        this.next = null; 
    } 
} 
// A utility function to print 
// linked list 
function printList(node)  
{ 
    while (node != null)  
    { 
        document.write(node.data + " "); 
        node = node. next; 
    } 
    document.write("<br/>"); 
} 
//Function to create newNode 
// in a linked list 
function newNode(key)  
{ 
    var temp = new Node(); 
    temp.data = key; 
    temp.next = null; 
    return temp; 
} 
//Function to insert at the beginning 
function insertBeg(head, val)  
{ 
    var temp = newNode(val); 
    temp.next = head; 
    head = temp; 
    return head; 
} 
//Function to rearrange the 
// odd and even nodes 
function rearrange(head)  
{ 
    // Step 1: Segregate even and odd nodes 
    // Step 2: Split odd and even lists 
    // Step 3: Merge an even list into an odd list 
    var even; 
    var temp, prev_temp; 
    var i, j, k, l, ptr = null; 
    // Step 1: Segregate Odd and   
    // Even Nodes 
    temp = (head). next; 
    prev_temp = head; 
    while (temp != null)  
    { 
        // Backup next pointer of temp 
        var x = temp.next; 
        // If the temp is odd, move the node 
        // to the beginning of the list 
        if (temp. data % 2 != 0)  
        { 
            prev_temp.next = x; 
            temp.next = (head); 
            (head) = temp; 
        } 
        else 
        { 
            prev_temp = temp; 
        } 
        // Advance Temp Pointer 
        temp = x; 
    } 
    // Step 2 
    // Split the List into Odd and even 
    temp = (head).next; 
    prev_temp = (head); 
    while (temp != null &&  
           temp.data % 2 != 0)  
    { 
        prev_temp = temp; 
        temp = temp. next; 
    } 
    even = temp; 
    // End the odd List (Make last  
    // node null) 
    prev_temp.next = null; 
    // Step 3: 
    // Merge Even List into odd 
    i = head; 
    j = even; 
    while (j != null &&  
           i != null)  
    { 
        // While both lists are not 
        // exhausted Backup next 
        // pointers of i and j 
        k = i.next; 
        l = j.next; 
        i.next = j; 
        j.next = k; 
        // ptr points to the latest  
        // node added 
        ptr = j; 
        // Advance i and j pointers 
        i = k; 
        j = l; 
    } 
    if (i == null)  
    { 
        // Odd list exhausts before even, 
        // append remainder of even list 
        // to odd. 
        ptr.next = j; 
    } 
    // The case where even list exhausts  
    // before the odd list is automatically  
    // handled since we merge the event  
    // list into the odd list 
    return head; 
} 
// Driver Code 
var head = newNode(8); 
head = insertBeg(head, 7); 
head = insertBeg(head, 6); 
head = insertBeg(head, 3); 
head = insertBeg(head, 5); 
head = insertBeg(head, 1); 
head = insertBeg(head, 2); 
head = insertBeg(head, 10); 
document.write("Linked List:<br/>"); 
printList(head); 
document.write("Rearranged List<br/>"); 
head = rearrange(head); 
printList(head);

输出

上述代码的输出是

说明

提供的 JavaScript 代码演示了通过将链表节点分离成奇数或偶数节点，将它们解耦，然后合并偶数节点到奇数节点中来重新排列单链表。

Node 类定义了链表节点的结构，具有一个数据字段和一个指向下一个节点的指针。printList 函数用于显示链表的元素。

newNode 函数创建一个具有给定值的节点，并将新节点插入到链表的开头。

rearrange 函数执行重新排列过程。它首先通过将奇数节点移到前面来分离奇数或偶数节点。然后，它将链表分成奇数和偶数部分。最后，它将偶数列表合并到奇数列表中。

驱动代码创建链表，打印链表，执行 rearrange 函数的重新排列操作，然后打印修改后的链表。重新排列确保最终链表中奇数和偶数的相关元素是交替排列的。

结论

最后，实现 JavaScript 函数以交替的奇偶节点顺序排列单链表，展示了该语言在处理算法要求高的场景下的多功能性和有效性。所提供的方法利用链表的基本结构来有效地分离奇数或偶数节点，然后再将它们合并到所需的顺序中。

这个问题突出了对数据结构（特别是链表）的扎实掌握以及高效地分割和操纵节点的能力的重要性。JavaScript 的模块化和面向对象的性质，如代码所示，有助于解决方案的清晰性。

作为开发人员，对代码进行修改和扩展以处理类似的任务或探索更高级的算法将是可行的，这展示了 JavaScript 在解决各种编程挑战方面的强大功能。总的来说，本教程不仅解决了特定的链表重新排列问题，还作为 JavaScript 应用中算法问题的一个实际示例。

下一话题Javascript-frontend-frameworks

使用 JavaScript 以奇偶节点顺序排列单链表

引言

链表概述

问题陈述

方法

方法 1（简单）

实施

方法 2（高效）

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

JavaScript 基础

JS 变量和数据类型

JS 控制语句

JavaScript 函数

JavaScript 对象

JS 高级函数

JS Promises & Async/Await

JavaScript DOM

JavaScript JSON 对象

JavaScript 验证

JavaScript Cookies

异常处理

JavaScript 集合

JavaScript 事件

JavaScript OOPs

JavaScript BOM

面试题

选择题

差异

JavaScript Map 方法

JavaScript Handler

JavaScript Number 方法

JavaScript Reflect

JavaScript Symbol

Symbol 属性

JavaScript Math 方法

JavaScript Date 方法

JavaScript DataView

JavaScript Object 方法

JavaScript Set 方法

JavaScript 字符串方法

JavaScript TypedArray 方法

JavaScript WeakMap 方法

JavaScript WeakSet 方法

JavaScript 数组方法

JavaScript RegExp 对象

JavaScript 附加内容

JavaScript 杂项

JavaScript 进阶

问题

Lodash

使用 JavaScript 以奇偶节点顺序排列单链表

引言

链表概述

问题陈述

方法

方法 1（简单）

实施

方法 2（高效）

结论

相关帖子

检查 JavaScript 中的子字符串

JavaScript 中的 IIFE 是什么？

将 JSON 转换为 JavaScript 对象

JavaScript String trim()

如何免费学习 JavaScript

JavaScript 模板文字

最佳 JavaScript 游戏引擎

计算 JavaScript 中的平均值

React JavaScript 示例