day2--链表

1.链表是什么？

一组不必相连的内存结构，按特定顺序链接在一起的抽象数据类型
1.不必相连
2.节点

2.链表种类

单向链表：内存结构由数据域next指针域组成（单向遍历）
双向链表：通过指针Next 和指针 Prev 链接在一起组成
循环链表：每一个内存结构都有前驱后继

3.链表算法

//数组转链表
    function createLinkedList(arr) {
      let linkNode = [];
      function Node(val) {
        this.val = val;
        this.next = null;
      }
      for (let i = 0; i < arr.length; i++) {
        let node = new Node(arr[i]);
        linkNode.push(node);
      }
      for (let i = 0; i < linkNode.length - 1; i++) {
        linkNode[i].next = linkNode[i + 1];
      }
      let linkList = {};
      linkList.head = linkNode[0];
      return linkList;
    }

//链表倒数第k个节点
	var getKthFromEnd = function (head, k) {
      let current = head;
      let count = 0;
      while (current) {
        current = current.next;
        count++;
      }
      current = head;
      for (let i = 0; i < count - k; i++) {
        current = current.next
      }
      return current
    };

//求离终点距离为 k 的节点
    function findNode(list, k) {
      let len = 0;
      let current = list.head;
      while (current) {
        current = current.next;
        len++;
      }
      return len - k;
    }

//翻转链表
    function reverseList(list) {
      let current = list.head
      let prev = null
      while (current) {
        let next = current.next;
        current.next = prev
        prev = current
        current = next;
      }
      return prev;
    }

//判断是否是回文链表
    function isPalindrome(head) {
      let current = head;
      let ans = []
      while (current) {
        ans.push(current.val);
        current = current.next;
      }
      let len = ans.length;
      let len1 = Math.floor(ans.length / 2);
      for (let i = 0; i < len1; i++) {
        if (ans[i] != ans[len - 1 - i]) {
          return false;
        }
      }
      return true;
    }

//从尾到头打印链表
    function printListFromTailToHead(list) {
      let ans = [];
      let current = list;
      while (current) {
        ans.push(list.val);
        current = current.next;
      }
      return ans.reverse();
    }

//合并两个有序链表
    function mergeTwoLists(l1, l2) {
      if (l1 === null) return l2;
      if (l2 === null) return l1;
      if (l1.val > l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
      } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
      }
    }