linkedList.ts

// 单向链表

/**
 * 链表节点
 */
export class ListNode {
  [x: string]: any;
  constructor(data: any) {
    this.data = data; // 数据
    this.next = null; // 指向下一个节点的指针
  }
  // 转数组
  toArr() {
    const arr = [];
    let p = this;
    while (p) {
      arr.push(p.data);
      p = p.next;
    }
    return arr;
  }
}

/**
 * 链表类
 * 通常使用"head"作为链表的入口，这个"head"是对链表中第一个节点的引用，
 * 而链表的最后一个节点指向null,
 * 如果是空链表，链表的引用就是null
 */
export class LinkedList {
  [x: string]: any;
  // 果未传递"head"节点，则它将初始化为 null
  constructor(head: any = null) {
    // this.head = head;
    if (head) {
      this.head = new ListNode(head);
    } else {
      this.head = null;
    }
  }
  // 添加节点
  add(data: any) {
    const newNode = new ListNode(data);
    const currNode = this.getLast();
    if (currNode) {
      // 将最后一个节点的指针指向新的节点
      currNode.next = newNode;
    } else {
      this.head = newNode;
    }
  }
  // 查找节点
  find(data: any) {
    let currNode = this.head; // 从头部开始找
    while (currNode && currNode.data !== data) {
      // 如果不相等，则指针指向下一个节点继续比较
      currNode = currNode.next;
    }
    return currNode;
  }
  // 插入节点
  // target:链表中存在的节点值
  // data:要插入的节点值
  // data插入的位置在target的后面
  insert(target: any, data: any) {
    const tagNode = this.find(target);
    if (!tagNode) return; // 如果目标节点不存在，则返回
    const newNode = new ListNode(data);

    newNode.next = tagNode.next; // 1 先将新节点的指针->指向目标节点的next
    tagNode.next = newNode; // 2 再将目标节点的指针指向->新节点
    // 注意顺序不要反了，不然目标节点与新节点的指针会相互循环指向下去
  }
  // 删除节点
  remove(data: any) {
    const tarNode = this.find(data);
    if (!tarNode) return; // 删除的节点不存在，就返回

    if (this.head.data === data) {
      // 如果是头节点
      console.warn('单链表的头节点不允删除');
      return;
    }

    // 方法一
    // 找到要删除节点的前一个节点(例如叫A节点)
    // 还是从头开始找
    let currNode = this.head;

    // 如果A节点的下一个指针指向的节点值等于我们要删除的节点值，那么这个节点就是我们要找的
    while (currNode && currNode.next && currNode.next.data !== data) {
      currNode = currNode.next;
    }
    // 然后把A节点的next指向->删除节点的next
    currNode.next = tarNode.next;

    // // 方法二
    // // 此方法不能删除最后一个节点
    // // 将要删除节点的值修改为它的下一个节点的值
    // if (tarNode.next) {
    //   tarNode.data = tarNode.next.data;
    //   tarNode.next = tarNode.next.next;
    // }
  }
  // 链表反向
  reverse() {
    if (this.head === null || this.head.next === null) {
      return this.head;
    }
    let p = this.head;
    let n = null;
    while (p) {
      const nextNode = p.next;
      p.next = n;
      n = p;
      p = nextNode;
    }
    const newList = new LinkedList();
    newList.head = n;
    return newList;
  }
  // 返回链表中的节点数
  size() {
    let count = 0;
    let node = this.head;
    while (node) {
      count++;
      node = node.next;
    }
    return count;
  }
  // 清空链表
  clear() {
    this.head = null;
  }
  // 返回链表的最后一个节点
  getLast() {
    let lastNode = this.head;
    if (lastNode) {
      while (lastNode.next) {
        lastNode = lastNode.next;
      }
    }
    return lastNode;
  }
  // 返回链表的第一个节点
  getFirst() {
    return this.head;
  }
  // 返回上一个节点
  getLastNode(data: any) {
    const currNode = this.find(data);
    if (currNode) {
      // 如果头节点
      if (data === this.head.data) {
        return null;
      } else {
        let currNode = this.head;
        while (currNode && currNode.next && currNode.next.data !== data) {
          currNode = currNode.next;
        }
        return currNode;
      }
    } else {
      return null;
    }
  }
  // 返回下一个节点
  getNextNode(data: any) {
    const currNode = this.find(data);
    if (currNode) {
      return currNode.next;
    } else {
      return null;
    }
  }
  // 返回链表的中间节点
  // 如果有两个中间节点，则返回第二个节点
  getMiddle() {
    // 用两个指针，快指针走两步，慢指针走一步
    // 当快指针到终点时，慢指针正好在中间
    let fast = this.head;
    let low = this.head;
    while (fast && fast.next) {
      fast = fast.next.next;
      low = low.next;
    }
    return low;
  }
  // 转数组
  toArr() {
    let p = this.head;
    const arr = [];
    while (p) {
      arr.push(p.data);
      p = p.next;
    }
    return arr;
  }
}

/**
 * 合并两个升序链表
 */
export const mergeTwoLists = function (list1: any, list2: any) {
  let p1 = list1.head || null;
  let p2 = list2.head || null;
  const newList = new LinkedList('head');
  let p3 = newList.head;
  while (p1 && p2) {
    // 把更小的放到p3，p3向后移动，小的那个也向后移动
    if (p1.data > p2.data) {
      p3.next = p2;
      p2 = p2.next;
    } else {
      p3.next = p1;
      p1 = p1.next;
    }
    p3 = p3.next;
  }
  p3.next = p1 ? p1 : p2;
  // while (p1) {
  //   p3.next = p1;
  //   p3 = p3.next;
  //   p1 = p1.next;
  // }
  // while (p2) {
  //   p3.next = p2;
  //   p3 = p3.next;
  //   p2 = p2.next;
  // }

  return newList.head.next;
};

/**
 * 合并两个升序链表 递归法
 */
export const mergeByRecursion = function (list1: any, list2: any) {
  const p1 = list1 ? list1.head || list1 : null;
  const p2 = list2 ? list2.head || list2 : null;
  if (p1 === null) {
    return p2;
  }
  if (p2 === null) {
    return p1;
  }
  if (p1.data < p2.data) {
    p1.next = mergeByRecursion(p1.next, p2);
    return p1;
  } else {
    p2.next = mergeByRecursion(p2.next, p1);
    return p2;
  }
};

/**
 * 两数相加
 */
export const addTwoNumbers = function (l1: any, l2: any) {
  let p1 = l1.head || null;
  let p2 = l2.head || null;
  const list3 = new ListNode('head');
  let p3 = list3;
  let step = 0;
  while (p1 || p2) {
    const sum = (p1?.data || 0) + (p2?.data || 0) + step;
    const targetNum = sum % 10; // 当前位的值
    p3.next = new ListNode(targetNum);
    p1 = p1?.next || null;
    p2 = p2?.next || null;
    p3 = p3.next;
    step = Math.floor(sum / 10); // 下一次的进位数
    if (p1 == null && p2 == null && step !== 0) {
      p3.next = new ListNode(step);
    }
  }
  return list3.next;
};

/**
 * 移除链表元素
 */
export const removeElements = function (head: any, val: any) {
  // 方法一 迭代
  // let p = head;
  // while (p) {
  //   if (p.next?.data === val) {
  //     p.next = p.next.next || null;
  //   } else {
  //     if (p.next) {
  //       p = p.next;
  //     } else {
  //       p = null;
  //     }
  //   }
  // }
  // if (head?.data === val) {
  //   head = head.next || null;
  // }
  // return head;

  // 方法二 递归
  if (head === null) {
    return null;
  }
  head.next = removeElements(head.next, val);
  return head.data === val ? head.next : head;
};