线性表-链表

链表是物理存储单元上非连续的，非顺序的存储结构，由一系列节点组成。

• 单向链表的实现
• 链表的应用

单向链表的实现

实例代码

function LinkList() {
  // 定义节点
  var Node = function (data) {
    this.data = data;
    this.next = null;
  };
  var length = 0; // ⻓度
  var head = null; // 头节点
  var tail = null; // 尾节点
  // 添加⼀个新元素
  this.append = function (data) {
    // 创建新节点
    var node = new Node(data);
    // 如果是空链表
    if (head == null) {
      head = node;
      tail = head;
    } else {
      tail.next = node; // 尾节点指向新创建的节点
      tail = node; // tail指向链表的最后⼀个节点
    }
    length += 1; // ⻓度加1
    return true;
  };
  // 返回链表⼤⼩
  this.length = function () {
    return length;
  };
  // 在指定位置插⼊新的元素
  this.insert = function (index, data) {
    if (index == length) {
      return this.append(data);
    } else if (index > length || index < 0) {
      return false;
    } else {
      var new_node = new Node(data);
      if (index == 0) {
        new_node.next = head;
        head = new_node;
      } else {
        var insert_index = 1;
        var curr_node = head;
        // 找到应该插⼊的位置
        while (insert_index < index) {
          curr_node = curr_node.next;
          insert_index += 1;
        }
        var next_node = curr_node.next;
        curr_node.next = new_node;
        new_node.next = next_node;
      }
      length += 1;
      return true;
    }
  };
  // 删除指定位置的节点
  this.remove = function (index) {
    if (index < 0 || index >= length) {
      return null;
    } else {
      var del_node = null;
      if (index == 0) {
        // head指向下⼀个节点
        del_node = head;
        head = head.next;
      } else {
        var del_index = 0;
        var pre_node = null;
        var curr_node = head;
        while (del_index < index) {
          del_index += 1;
          pre_node = curr_node;
          curr_node = curr_node.next;
        }
        del_node = curr_node;
        pre_node.next = curr_node.next;
        // 如果删除的是尾节点
        if (curr_node.next == null) {
          tail = pre_node;
        }
      }
      length -= 1;
      del_node.next = null;
      return del_node.data;
    }
  };
  // 删除尾节点
  this.remove_tail = function () {
    return this.remove(length - 1);
  };
  // 删除头节点
  this.remove_head = function () {
    return this.remove(0);
  };
  // 返回指定位置节点的值
  this.get = function (index) {
    if (index < 0 || index >= length) {
      return null;
    }
    var node_index = 0;
    var curr_node = head;
    while (node_index < index) {
      node_index += 1;
      curr_node = curr_node.next;
    }
    return curr_node.data;
  };
  // 返回链表头节点的值
  this.head = function () {
    return this.get(0);
  };
  // 回链表尾节点的值
  this.tail = function () {
    return this.get(length - 1);
  };
  // 返回指定元素的索引,如果没有,返回-1，有多个相同元素,返回第⼀个
  this.indexOf = function (data) {
    var index = -1;
    var curr_node = head;
    while (curr_node) {
      index += 1;
      if (curr_node.data == data) {
        return index;
      } else {
        curr_node = curr_node.next;
      }
    }
    return -1;
  };
  // 输出链表
  this.print = function () {
    var curr_node = head;
    var str_link = "";
    while (curr_node) {
      str_link += curr_node.data.toString() + " ->";
      curr_node = curr_node.next;
    }
    str_link += "null";
    console.log(str_link);
    console.log("⻓度为" + length.toString());
  };
  // isEmpty
  this.isEmpty = function () {
    return length == 0;
  };
  // 清空链表
  this.clear = function () {
    head = null;
    tail = null;
    length = 0;
  };
}

链表的应用

1. 快乐数 - LeetCode 连接

   编写一个算法来判断一个数 n 是不是快乐数。
   - 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
   - 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
   - 如果 可以变为  1，那么这个数就是快乐数。
   - 如果 n 是快乐数就返回 true ；不是，则返回 false 。
   

   实例代码

   class Solution {
    public boolean isHappy(int n) {
     int p = n;
     int q = n;
     do {
      p = getNext(p);
      q = getNext(getNext(q));
     } while (p!=q && q != 1);
     return q==1;
    }
    public int getNext (int x){
     int z = 0;
     while(x != 0){
      z += (x % 10) * (x % 10);
      x /= 10;
     }
     return z;
    }
   }