【数据结构】JavaScript实现单链表、单链表反转

待我称王封你为后i 2022-05-16 02:23 277阅读 0赞

### 链表 ###

链接也是一种存储数据的工具，不同于数组，链表中的元素并不是连续存储的。因此不能通过下标去访问。 链表分为单(向)链表，双向链表，循环链表等。.今天来实现一下单链表。  
单链表中的每个元素包括两个两个域，一个是保存元素本身的域，另一个是指向一下一个节点的指针域

function LinkedList(){ 
            var Node = function( ele ){ 
                this.ele = ele;     //ele 属性代表插入的值
                this.next = null;   // next属性 代表 指向下一个节点的指针
            }
            var head = null;
            var length = 0;
    
    
            // 向链表末尾插入一个元素
            this.append = function(ele){ 
                var node = new Node(ele);
                var currentNode = null;
    
                if( head === null){    // 列表为空，插入的节点是第一个头结点
                    head = node;
                }
                else{
                    currentNode = head;
                    // 循环链表，直到最后一个节点
                    while( currentNode.next !== null ){
                        currentNode = currentNode.next;
                    }
                    // 出了while循环，说明找到了最后一个节点
                    currentNode.next = node;
    
                }
                length++;
            }
            // 删除链表中指定的某个节点:删除头结点 or 除了头结点以外的节点
            this.removeAt = function( position ){ 
                var currentNode = head;
                var previousNode = null;
                var index = 0;
    
                if( position >= 0 && position < length ){
                    if( position === 0 ){
                        node = currentNode.next;
                    }
                    else{
                        while( index++ < position ){
                            previousNode = currentNode;
                            currentNode = currentNode.next;
                        }
                        // 出了while循环， index === position
                        previousNode.next = currentNode.next;
                    }
                    length--;
                    return currentNode.ele
                }
                // 要删除的节点的不存在
                else{
    
                    return -1;
                }
            }
            // 在任意位置插入一个元素
            this.insert = function(){ 
                // 检查是否越界
                if( position >= 0 && position <= length ){
                    var newNode = new Node(ele);
                    var currentNode = head;   // 保存一下头结点
                    var previousNode = null;
                    var index = 0;
    
                    if( position === 0 ){
                       newNode.next = currentNode;
                       head = newNode;
                    }
                    else{
                        while ( index++ < position ){
                            previousNode = currentNode;
                            currentNode = currentNode.next;
                        }
                        // 出了循环表示找到位置
                        newNode.next = currentNode;
                        previousNode.next = currentNode;
                    }
                    length++;
                    return 1;
                }
                else{
                    return -1;
                }
            }
    
            //查找链表中的某个元素所在位置， 无此元素返回 -1
            this.find = function(ele){ 
                 var currentNode = head;
                 var index = 0;
                 while( currentNode ){
                    if( currentNode.ele = ele ){
                        return index;
                    }
                    currentNode = currentNode.next;
                    index++; 
                }  
                return -1;
            }       
    
            this.isEmpty = function(){ 
                return length === 0;
            }
    
            this.size = function(){ 
                return length;
            }
    
        }

**下面来实现链表的反转**

function reverse( linkedList ){ 
        var head = linkedList.head;
    
        // 如果只有一个节点 或者 是空链表
        if( head === null || head.next === null ){
            return;
        }
        var p = head;
        var q = p.next;
        // 反转后的头结点变成尾节点
        head.next = null;
        while(q){
            r = q.next;
            q.next = p;
            p = q;
            q = r;
        }
        // 退出循环后 r = q.next = null, q.next = q; p=q; q=null;
        // p指向原来节点的尾节点， 那么翻转后，尾节点变成头结点
        linkedList.head = p;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，277人围观）

还没有评论，来说两句吧...

相关阅读

相关反转单链表

[https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&rp=1&ru=%2Ft

本是古典何须时尚/ 2022年11月30日 01:46/ 0 赞/ 265 阅读

相关单链表反转

include<iostream> using namespace std; typedef struct node { i

刺骨的言语ヽ痛彻心扉/ 2022年09月18日 04:47/ 0 赞/ 239 阅读

相关单链表反转

把每次翻转看成左右两个部分的翻转，比如第一次翻转时把左边的第一个节点看成左部分，把右边的第二个节点看成右部分，来进行翻转，第二次翻转时把左边的两个节点看成一个左部分，右边的第三

本是古典何须时尚/ 2022年08月09日 01:55/ 0 赞/ 246 阅读

相关反转单链表

前插 class ListNode { int val; ListNode next; ListNode(i

Bertha 。/ 2022年08月04日 04:18/ 0 赞/ 269 阅读

相关反转单链表

![这里写图片描述][70] //解法一:反转链表 public ListNode reverseList(ListNode head){

以你之姓@/ 2022年05月23日 04:36/ 0 赞/ 281 阅读

相关【数据结构】JavaScript实现单链表、单链表反转

链表链接也是一种存储数据的工具，不同于数组，链表中的元素并不是连续存储的。因此不能通过下标去访问。链表分为单(向)链表，双向链表，循环链表等。.今天来实现一下单链表。

待我称王封你为后i/ 2022年05月16日 02:23/ 0 赞/ 278 阅读

相关数据结构 - 反转单链表（C++）

分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangju

旧城等待，/ 2022年04月22日 05:08/ 0 赞/ 298 阅读

相关单链表反转

单链表的翻转是一道很基本的算法题。方法1：将单链表储存为数组，然后按照数组的索引逆序进行反转。方法2：使用三个指针遍历单

悠悠/ 2022年03月09日 11:26/ 0 赞/ 322 阅读

相关数据结构：单链表实现反转

实现思路： 1. 如果链表只有一个或者没有节点，则无需反转 2. 原链表的第一个节点即为反转后的最后一个元素，需要将其固定，我们叫它final 3. 按原链表的顺序

悠悠/ 2021年12月16日 14:13/ 0 赞/ 360 阅读

相关数据结构--线性表的链式存储结构（单链表完全实现）、单链表反转

线性表的链式存储结构 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9

阳光穿透心脏的1/2处/ 2021年08月14日 01:41/ 0 赞/ 491 阅读