JS数据结构之单向循环链表

数据结构

发布日期: 2021-07-13

文章字数: 3.2k

之前我们们已经了解并且实现过单向链表，但是实际上单向链表只是最简单最基础的链表结构，在实际应用中我们还能接触到很多其他的链表结构。今天我们就来探索一下单向循环链表~

单向循环链表

单向循环链表和单向链表的结构基本一致，唯一的不同之处在于单向链表最后一个节点的指针的next属性指向null，而单向循环链表的最后一个节点的next指针指向链表的头节点，这也就是单向循环链表名称的由来。单向循环链表的结构图如下所示：

循环链表示意图

下面我们就来实现一下单向循环链表，我们已经知道和单向链表相比，单向循环链表的节点和链表结构没有任何区别，所以我们可以直接用单向链表的结构定义。当然，这里也可以使用继承，然后重写父类的方法即可。这里为了阅读方便，我就直接把单向链表的数据结构定义拷过来了：

class Node {
    constructor(element, next) {
    this.element = element; // 当前节点保存的值
    this.next = next; // 指向下一个节点
    }
}

class LinkedList {
    constructor() {
    // 链表的头节点
    this.head = null;
    // 链表的长度
    this.size = 0;
    }
}

接着我们就来实现单向循环链表的增、删、改、查功能。

查(getNode)

在查找节点的时候需要注意的是，因为单向循环链表是循环的，如果给的索引范围超过链表的长度，遍历一次之后没有找到指定的索引，则会从头继续遍历从而返回错误的结果，所以这里需要通过判断是否已经查找到最后一个节点来及时终止循环。这个逻辑我们之前也做过，这里就不再赘述。
除了实现根据索引来查找节点的方法之外，这里我们还实现了一种根据值来查找节点的方法 find，这个方法也非常简单，核心思想依然是遍历，只不过多了个比较节点值的逻辑。这个方法有 2 个需要注意的地方：1、用这种方法实现的 find 在多个节点保存的值相同时候，只能找到第 1 个符合条件的节点；2、在节点中保存的数据为引用类型的时候，find 可能会得不到我们想要的结果；代码如下：

// 根据索引查找
getNode(index) {
  let offset = 0;
  let curNode = this.head;
  if (index >= this.size)
    return new Error("Index exceeds the range of the linked list");
  while (offset++ < index) {
    curNode = curNode.next;
  }
  return curNode;
}
// 根据值查找
find(item) {
  let offset = 0;
  let curNode = this.head;
  while (offset++ < this.size) {
    if (curNode.element === item) return curNode;
    curNode = curNode.next;
  }
}

增(add)

和单向链表不同的是，单向循环链表在增加节点时需要考虑到如果是在头尾增加节点则需要更新最后一个节点的next指针，而且在头节点插入节点的时候还需要考虑空链表的情况。所以增加节点一共有三种情况(图中绿色线条表示更新的操作)：

在表头插入节点
- 链表为空；这种情况下，链表的头尾节点都为新增节点，链表改动操作如下：
- 链表不为空；这种情况下，我们需要将新增节点作为头节点，并将其 next 指向旧的头节点，然后更新最后一个节点的 next，将其指向新的头节点；如下图所示：
在末尾插入节点；这种场景下需要注意除了将节点插入之外还要将节点的 next 指向链表头部，如下图所示：
其他情况；需要先找到对应的索引的前一个节点，将前一个节点的 next 指向新增的节点，并将新增节点的 next 指向前一个节点原本的 next 节点；

代码如下：

add(index, element) {
   // 如果只传一个值则默认在最后插入
   if (arguments.length === 1) {
     element = index;
     index = this.size;
   }
   if (index === 0) {
     const oldHead = this.head;
     // 最后一个节点
     const lastNode = this._getLastNode();
     const newHead = new Node(element, oldHead);
     this.head = newHead;
     // 更新节点指针，需要判断为空列表的时候
     if (lastNode) {
       lastNode.next = newHead;
     } else {
       // 为空链表时
       newHead.next = this.head;
     }
   } else if (index === this.size - 1) {
     const head = this.head;
     const lastNode = this._getLastNode();
     const newNode = new Node(element, head);
     lastNode.next = newNode;
   } else {
     const prevNode = this._getNode(index - 1);
     prevNode.next = new Node(element, prevNode.next);
   }
   this.size++;
 }

改(update)

因为我们前面在查找结点的时候就排除过索引超出链表长度的情况，所以这里不用再考虑索引超出范围的情况。这个功能的代码和单向链表的一样:

//  更新节点信息
update(index, element) {
  const updateNode = this._getNode(index);
  updateNode.element = element;
  return updateNode;
}

删(remove)

和增加节点方法类似，删除节点的方法相较于单向链表也需要注意一下删除头节点时的情况，和增加节点一样，我们也分为几种情况讨论：

删除的是头节点
- 链表长度为 1 时；此时清空链表即可；
- 链表长度不为 1 时；此时需要将原头节点的 next 指向的节点作为新的头节点，并将链表最后一个节点的 next 指向新的头节点。具体操作如下图：
删除其他节点；此时需找到待删除节点的前一个节点，将前一个节点的 next 指向待删除节点的 next 节点；如下图所示：

删除这里也和前文的查找节点的方法一样，实现了两种，一种是根据索引删除节点(remove)；另一种是根据节点的值删除节点 (removeNode)；而第二种方法也仍然存在和 find 方法一样的限制。代码如下：

// 节点删除
  remove(index) {
    let removeNode;
    if (index >= this.size) return new Error("Index out of range");
    if (index === 0) {
        // 删除头节点
      removeNode = this.head;
        // 如果是空链表
      if (!removeNode) return removeNode;
      if (this.size === 1) {
        // 只有一个节点，则置空链表；
        this.head.next = null;
        this.head = null;
      } else {
        const lastNode = this._getLastNode();
        this.head = this.head.next;
        lastNode.next = this.head.next;
      }
    } else {
      const prevNode = this._getNode(index - 1);
      removeNode = prevNode.next;
      prevNode.next = prevNode.next.next;
    }
    this.size--;
    return removeNode;
  }
  // 根据值删除对应的节点
  removeNode(item) {
    let removeNode = this.find(item); // 找到待删除节点
    let lastNode = this._getLastNode(); // 找到最后一个节点
    let preCurNode = this.head;
    // 找到待删除节点的前一个节点
    while (preCurNode.next !== removeNode) {
      preCurNode = preCurNode.next;
    }

    if (removeNode == this.head) {
      // 如果当前节点是第一个节点
      //头结点的后一个节点
      if (this.size == 1) {
        //只剩最后一个节点
        this.head = null;
      } else {
        //还有其他节点
        this.head = this.head.next;
        lastNode.next = this.head;
      }
    } else {
      // 其他情况
      preCurNode.next = preCurNode.next.next;
    }
    this.size--;
    return removeNode;
  }

完整代码

class Node {
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}

class CircleLinkedList {
  constructor() {
    // 链表的头指针
    this.head = null;
    // 链表的长度
    this.size = 0;
  }
  _getNode(index) {
    let offset = 0;
    let curNode = this.head;
    if (index >= this.size)
      return new Error("Index exceeds the range of the linked list");
    while (offset++ < index) {
      curNode = curNode.next;
    }
    return curNode;
  }
  _getLastNode() {
    // 如果链表为空，则返回头节点即可
    if (this.size === 0) return this.head;
    return this._getNode(this.size - 1);
  }
  getNode(index) {
    return this._getNode(index);
  }
  add(index, element) {
    // 如果只传一个值则默认在最后插入
    if (arguments.length === 1) {
      element = index;
      index = this.size;
    }
    if (index === 0) {
      const oldHead = this.head;
      // 最后一个节点
      const lastNode = this._getLastNode();
      const newHead = new Node(element, oldHead);
      this.head = newHead;
      // 更新节点指针，需要判断为空列表的时候
      if (lastNode) {
        lastNode.next = newHead;
      } else {
        // 为空链表时
        newHead.next = this.head;
      }
    } else if (index === this.size) {
      const head = this.head;
      const lastNode = this._getLastNode();
      const newNode = new Node(element, head);
      lastNode.next = newNode;
    } else {
      const prevNode = this._getNode(index - 1);
      prevNode.next = new Node(element, prevNode.next);
    }
    this.size++;
  }
  //  更新节点信息
  update(index, element) {
    const updateNode = this._getNode(index);
    updateNode.element = element;
    return updateNode;
  }
  // 节点删除
  remove(index) {
    let removeNode;
    if (index >= this.size) return new Error("Index out of range");
    if (index === 0) {
      // 删除头节点
      removeNode = this.head;
      // 如果是空链表
      if (!removeNode) return removeNode;
      if (this.size === 1) {
        // 只有一个节点，则置空链表；
        this.head = null;
      } else {
        const lastNode = this._getLastNode();
        this.head = this.head.next;
        lastNode.next = this.head.next;
      }
    } else {
      const prevNode = this._getNode(index - 1);
      removeNode = prevNode.next;
      prevNode.next = prevNode.next.next;
    }
    this.size--;
    return removeNode;
  }
  find(item) {
    let offset = 0;
    let curNode = this.head;
    while (offset++ < this.size) {
      if (curNode.element === item) return curNode;
      curNode = curNode.next;
    }
  }
  removeNode(item) {
    let removeNode = this.find(item); // 找到待删除节点
    let lastNode = this._getLastNode(); // 找到最后一个节点
    let preCurNode = this.head;
    // 找到待删除节点的前一个节点
    while (preCurNode.next !== removeNode) {
      preCurNode = preCurNode.next;
    }

    if (removeNode == this.head) {
      // 如果当前节点是第一个节点
      //头结点的后一个节点
      if (this.size == 1) {
        //只剩最后一个节点
        this.head = null;
      } else {
        //还有其他节点
        this.head = this.head.next;
        lastNode.next = this.head;
      }
    } else {
      // 其他情况
      preCurNode.next = preCurNode.next.next;
    }
    this.size--;
    return removeNode;
  }
  advance(n, node) {
    let curNode = node;
    if (!node) {
      curNode = this.head;
      n--;
    }
    if (!n) return curNode;
    while (n-- && curNode.next) {
      curNode = curNode.next;
    }
    return curNode;
  }
}

相关面试题

1. 约瑟夫环

问题描述：

在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从，Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。

所以问题就是：在 n 个人围成一圈玩游戏，由第一个人开始报数，每报数到 m ，该人就被淘汰，直到剩下 s 个人为止时。那么在这场游戏中，想要留到最后的话应该站到什么位置呢？(假设 s 小于 n)。

解题思路：利用单向循环链表的特点，找到对应该删除的节点删除，直到链表长度达到指定值；

代码：

// n 个人围成一圈，报 m 个数，
function playGame(n, m, s) {
  const gameList = new CircleLinkedList();
  // 构建循环链表
  for (let index = 1; index <= n; index++) {
    gameList.add(index);
  }
  let curNode = undefined;
  let removeNode = null;
  while (gameList.size > s) {
    removeNode = gameList.advance(m, curNode);
    curNode = removeNode;
    gameList.removeNode(removeNode.element);
  }
  return gameList;
}

2. 发牌问题

问题描述：

魔术师手中有 A、2、3……J、Q、K 十三张黑桃扑克牌。在表演魔术前，魔术师已经将他们依照一定的顺序叠放好（有花色的一面朝下）。魔术表演过程为：一开始，魔术师数 1，然后把最上面的那张牌翻过来，是黑桃 A；然后将其放到桌面上；第二次,魔术师数 1、2；将第一张牌放到这些牌的最以下，将第二张牌翻转过来，正好是黑桃 2；第三次，魔术师数 1、2、3；将第 1、2 张牌依次放到这些牌的最以下，将第三张牌翻过来正好是黑桃 3；以此类推，直到将全部的牌都翻出来为止。问原来牌的顺序是怎样的。

解题思路：

首先建立一个长度为 13 的单向循环链表，当魔术师数 1 的时候翻开是黑桃 A，也就是说 A 为链表的第一个节点；
第二次,魔术师数 1、2；将第一张牌放到这些牌的最以下，这里相当于把链表的第一个节点取出来插入到链表的末尾，然后翻开下一张牌是 2，也就是说在将一个节点取出并插入到末尾之后此时链表的第一个节点为 2；实际上这里并不需要真的将节点取出再插入，因为单向循环链表本身就有循环的特点，这里我们只需要按照一定的规则跳过节点即可，这里需要跳过的节点就是魔术师放到最底下的牌(也即是需要取出并插入到末尾的节点)；
同理，第三次则是需要跳过两个节点，下一个节点的值就为 3；
按照规律，链表中所有的节点都被赋值之后，得到的链表中节点的顺序就是魔术师扑克牌的排列顺序；

代码：

// 魔术师发牌
const cardArr = [
  "A",
  "2",
  "3",
  "4",
  "5",
  "6",
  "7",
  "8",
  "9",
  "10",
  "J",
  "Q",
  "K",
];
function magicCard() {
  const magicCardList = new CircleLinkedList();
  // 进行13次循环，构建一个长度为13的空链表
  for (let index = 0; index < 13; index++) {
    magicCardList.add("");
  }
  // 记录当前为第几次翻牌
  let n = 1;
  // 记录当前更新的节点(要翻的那张牌)
  let curCard;
  while (n <= 13) {
    // 记录要跳过的节点数(也就是放到底部的牌数)
    let forward = n;
    while (forward > 0) {
      curCard = magicCardList.advance(1, curCard);
      if (!curCard.element) forward--;
    }
    curCard.element = cardArr[n - 1];
    n++;
  }
  return magicCardList;
}