跳到主要内容

单向链表

设计实现单链表: 单链表中的节点应该具有两个属性: val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。链表功能如下:

  • get(index): 获取链表中第 index 个节点的值。如果索引无效，则返回 -1

  • addAtHead(val): 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点

  • addAtTail(val): 将值为 val 的节点追加到链表的最后一个元素

  • addAtIndex(index,val): 在链表中的第 index 个节点之前添加值为 val 的节点 如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点

  • deleteAtIndex(index): 如果索引 index 有效，则删除链表中的第 index 个节点

基本操作​

操作一、构建单链表链表节点结构​

  • head 哨兵伪头节点
  • length 记录链表长度

注意: 构建链表时，设置伪头节点后删除第一个节点和删除其他节点相同，不用分情况讨论；如果没有伪头节点，那么删除节点时需要讨论是否为头节点。

constructor(){
  this.head=new Node(0);
  this.length=0;
}

操作二、在链表的第一个元素之前添加一个值为 val 的节点​

addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

addAtHead(val){
  this.addAtIndex(0,val);
}

操作三、将值为 val 的节点追加到链表的最后一个元素​

addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

addAtTail(val){
  this.addAtIndex(this.length,val);
}

操作四、在链表中的第 index 个节点之前添加值为 val 的节点​

addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

addAtIndex(index,val){
  if(index>this.length){
    return
  }
  if(index<0){
    index=0;
  }
  let prev=this.getPrev(index);
  let newNode=new Node(val);
  newNode.next=prev.next;
  prev.next=newNode;
  this.length++
}

操作五、获取链表中第 index 个节点的值​

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1

get(index){
  if(index<0||index>=this.length){
    return -1
  }
  let current=this.getPrev(index);
  return current.next.val
}

操作六、获取链表中第 index 个节点的前一个节点​

get(index)：获取链表中第 index 个节点的前一个节点。如果索引无效，则返回 null

getPrev(index){
  let prev=this.head;
  for(let i=0;i<index;i++){
    prev=prev.next;
  }
  return prev
}

操作七、删除链表中的第 index 个节点​

deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点

deleteAtIndex(index){
  if(index<0||index>=this.length){
    return null
  }
  let prev=this.getPrev(index);
  prev.next=prev.next.next;
  this.length--;
}

操作八、获取链表中 val 值为 x 的节点​

getByVal(val) {
  const current = this.getPrevByVal(val);
  return current.next;
}

操作九、获取链表中 val 值为 x 的前一个节点​

getPrevByVal(val) {
  let prev = new Node(0);
  prev.next = this.head;
  while (prev.next) {
    if (prev.next.val === val) {
      return prev;
    }
    prev = prev.next;
  }
}

完整代码​

class Node {
  val;
  next;
  constructor(val) {
    this.val = val;
  }
}
class MyLinkedList {
  constructor() {
    this.head = new Node(0);
    this.length = 0;
  }
  addAtHead(val) {
    this.addAtIndex(0, val);
  }
  addAtTail(val) {
    this.addAtIndex(this.length, val);
  }
  addAtIndex(index, val) {
    if (index > this.length) {
      return;
    }
    if (index < 0) {
      index = 0;
    }
    let prev = this.getPrev(index);
    let newNode = new Node(val);
    newNode.next = prev.next;
    prev.next = newNode;
    this.length++;
  }
  get(index) {
    if (index < 0 || index >= this.length) {
      return -1;
    }
    let current = this.getPrev(index);
    return current.next.val;
  }
  getPrev(index) {
    let prev = this.head;
    for (let i = 0; i < index; i++) {
      prev = prev.next;
    }
    return prev;
  }
  getByVal(val) {
    const current = this.getPrevByVal(val);
    return current.next;
  }
  getPrevByVal(val) {
    let prev = new Node(0);
    prev.next = this.head;
    while (prev.next) {
      if (prev.next.val === val) {
        return prev;
      }
      prev = prev.next;
    }
  }
  deleteAtIndex(index) {
    if (index < 0 || index >= this.length) {
      return null;
    }
    let prev = this.getPrev(index);
    prev.next = prev.next.next;
    this.length--;
  }
  show() {
    let current = this.head.next;
    let result = [];
    while (current) {
      result.push(current.val);
      current = current.next;
    }
    return result;
  }
}