前端校招准备系列--使用js实现链表的操作

前言

  在写项目的时候会发现，并没有使用很多关于链表的东西，大多数情况使用的都是数组，但是由于在准备校招，很多公司都会考到这个问题，所以准备对链表的相关操作进行总结，并对其中的重难点进行强调，最后还会附加几道关于链表的算法题，那么现在就开始吧！

链表的基础操作

创建一个链表结构

  了解过链表的同学应该都知道，链表有几个特点：

• 可以动态扩展空间（在js中，数组也是这样的，但是有的语言中数组的长度是固定的，不能动态添加，如c语言）
• 需要一个头节点
• 需要知道下一个节点的地址

  可以将链表中的每个节点看成是一个对象，这个对象中有两个属性，一个是该节点的值，一个是该节点的下一个节点的地址（如果是双链表，还要添加前一个节点地址的属性）

function LinkedList(){
      //辅助类：表示要加入链表的项
      let node = function(element){
        this.element = element;
        this.next = null;//这个节点的下一个节点暂时为空
      }

      let length = 0;
      let head = null;

      this.append() = function(element){};//向链表的尾部添加节点
      this.insert() = function(position,element){};//在指定的位置添加节点
      this.remove = function(element){};//将指定的节点删除掉
      this.removeAt = function(position){};//将指定位置的节点删除
      this.searchElement = function(element){};//查找指定元素的位置
      this.searchPosition = function(position){};//查找指定位置的元素
    }

  上面代码中包含了很多要实现的操作，包括最基本的增删以及查询。下面我们就来一一的实现上面列举的方法：

实现增加节点的操作

• 在尾节点处添加节点

function append(element){
    
     let node = new Node(element);//1

     let current;//2
     
     //3
     if(head === null){
       head = node
     }else{
       current = head
       while(current.next){
         current = current.next
       }
       current.next = node
     }
  
       length++;//4
    }

代码分析：

1. 根据传入的元素定义一个节点，该元素作为这个节点的值
2. 定义一个变量表示当前的节点
3. 判断是否含有头节点,如果没有头节点，说明链表中还没有值，将传进来的这个值作为头节点；否则，对链表进行遍历，找到最后一个节点，将其next属性赋值为新增的节点
4. 链表的长度+1

• 在任意位置添加节点

分析：

  将这个位置的前一个节点的next属性赋值为这个节点，并将它原先的下一个节点保存下来，赋值给现在这个节点的next属性

function insert(position,element){
      if(position >=0 && position <= length){
        //当position为length时，表示在尾节点处添加，包含了append方法
        let node = new Node(element);
        let current = head;
        let previous;//当前节点的前一个节点，在position处添加节点，就是在previos和current之间添加
        if(position = 0){
          node.next = head;
          head = node;
        }else{
          for(let i = 0;i< position;i++){
            pervious = current;
            current = current.next;
          }

          pervious.next = node;
          node.next = current;
        }
        length++;
        return true;
      }else{
        return false;
      }
    }

代码分析：

1. 检查postion是否越界,若没有越界，则创建一个节点
2. 定义一个变量表示当前的节点，初始化为头节点，表示从头节点开始遍历；一个变量表示当前节点的前一个节点，作用是插入节点时方便找到前一个节点
3. 判断是否在头节点前添加，如果是就将头节点赋给node的next属性，并且头节点改为这个节点；否则，遍历出这个位置的节点，将该节点插入到这个位置的节点前面
4. 链表的长度+1

实现删除节点的操作

  基本思路：删除节点的操作就是将目标节点前面的那个节点的指针指向目标节点的有一个节点

• 删除指定节点

function removed(element){
    
      let node = new Node(element);
      let pervious;
      let nextNode;
      let current = head;

    if(head != null){
      while (current != node){
        pervious = current;
        current = current.next;
        nextNode = current.next;
      }  

      pervious.next = nextNode;
      length--;
      return true;
    }else{
      return false;
    }    
    }

代码分析：重点在于抓住需要哪些节点，并且进行这个操作需要改变什么，判断条件是怎样的

• 删除指定位置的节点

function removedAt(position){
      //判断所给位置是否溢出
      if(position > -1 && position < length){
        let current = head;
        let pervious;
        let nextNode;
        let i = 0;

        while(i < position){
          pervious = current;
          current = current.next;
          nextNode = current.next;
        }

        pervious.next = nextNode;
        length--;
        return true;
      }else{
        return false;
      }
    }

实现查询节点的操作

  其实查询节点和删除节点差不多，都是通过遍历，找到相应的节点或是相应的位置，然后进行操作，说起来比删除节点还要简单

• 查询某个位置是哪个节点

function searchElement(element){
      //输入元素，找到该元素后返回该元素的位置
      if(head != null){
        let node = new Node(element);
        let current;
        let index = 0;
        if(head == node){
          return 0;
        }else{
          current = head;
          while(current != node){
            current = current.next;
            index++;
          }
          return index;
        }
      }else{
        return -1;
      }
    }

• 查询某个节点是在哪个位置

function searchPosition(position){
      //查找某一个位置的元素是什么
      if(position > -1 && position < length){
        let i = 0;
        let current = head;
        while(i< position){
          current = current.next;
          i++;
        }
        return current;
      }else{
        return null;
      }
    }

思路总结

  关于链表的操作还有很多，复杂一点的链表还有双链表（在初始化节点的时候增加一个前节点）和循环链表（尾节点的下一个节点是头节点），这些链表的操作也是可以使用js实现的，这里就不多说了。总结一下，链表的核心在于

• 链表中节点可看做一个对象，有两个属性值，一个是节点值，一个是指针
• 链表的增删就是改变指针指向
• 链表查找时，重点是current = current.next

有关链表的算法题

  这里总结几道在牛客网上的剑指offer中刷到的几道关于链表的算法题，这些题在笔试中还是很有可能遇到的，接着往下看吧！

1. 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

  思路：（1）将链表值从头到尾输出到一个数组中，然后将这个数组进行反转得到ArrayList
        （2）使用数组的unshift方法，将链表值倒序放进数组
        （3）先使用栈存放顺序遍历的结果，利用栈先进后出的特性，出栈的时候用数组保存

//使用思路2的方法
 function Node(element){
      this.val = element
      this.next = null
    }

    function logList(head){
      if(head != null){
        let ArrayList = [];
        while(head){
          ArrayList.unshift(head.element);
          head = head.next;
        }
        return ArrayList;
      }else{
        return [];
      }
    }

2. 输入一个链表，输出该链表中倒数第k个结点。

  思路：（1）查找倒数第k个节点，可以看做是查找正序第length-k个节点
        （2）可以根据第一题的结果取数组的第k-1个节点

//使用思路2
function Node(element){
    this.element = element;
    this.next = null;
}
function FindKthToTail(head, k)
{
        let array = []
        while(head != null){
        array.unshift(head)
        head = head.next;
    }

    return array[k-1];
}

3. 输入一个链表，反转链表后，输出新链表的表头。

  思路：把倒序后的链表放进一个数组中，然后将这个数组的每一位的next属性指向下一位

function ListNode(x){
    this.val = x;
    this.next = null;
}
function ReverseList(pHead)
{
  if(pHead){
        let arr = [];
        while(pHead){
            arr.unshift(pHead);
            pHead = pHead.next;
        }
        for(let i =0;i< arr.length;i++){
            arr[i].next = arr[i+1]
        }
        return arr[0]
    }
}

    本人的水平不佳，可能有些地方写错了，欢迎在评论中指出，大家一起进步哟！