js链表操作(实例讲解)

什么是链表

链表是一种基础数据结构，它由许多节点(Node)组成，每个节点都包含一个数据部分和一个指向下一个节点的指针。

链表可以看做是由多个节点组成的数据结构，每个节点包含元素值和指向下一个节点的指针属性。并且，链表可以表示各种抽象数据类型。链表中的第一个节点称为头节点。如果链表为空，则头节点为null。最后一个节点称为尾节点。尾节点的 next 属性为 null 。

相比较数组，链表的特殊之处在于它不需要在内存中占用连续的空间，这使得链表更加灵活，更适用于插入和删除操作。

链表的创建

链表可以从头节点开始创建，头节点是链表的起点。我们可以用一个对象来表示一个节点，其结构可以是这样的：

var ListNode = function(val) {
    this.val = val;
    this.next = null;
};

链表的遍历

链表遍历是指访问链表中的每个节点，可以用 while 循环实现链表的遍历。遍历链表中的每个节点时，可以对节点进行操作，或者获取节点的值。

var cur = head;
while(cur !== null) {
    console.log(cur.val);
    cur = cur.next;
}

链表的插入

链表的插入分为在首部插入、在中部插入和在尾部插入。在中部插入需要先找到要插入位置的节点，即前驱节点。其插入过程，可以分三步来实现：

• 在内存中创建一个新节点。
• 将新节点的 next 指针指向插入位置的节点。
• 将插入位置的前驱节点的下一节点 next 指针指向新节点。

var newNode = new ListNode(val);
if(position === 0) {
    newNode.next = head;
    return newNode;
} 

var cur = head;
var pre = null;
var index = 0;

while(index < position) {
    pre = cur;
    cur = cur.next;
    index++;
}

pre.next = newNode;
newNode.next = cur;

return head;

链表的删除

链表的删除分为三种情况：在首部删除、在中部删除和在尾部删除。在中部和尾部删除，需要找到要删除的节点的前驱节点。其删除过程，可以分三步来实现：

• 找到要删除节点的前驱节点。
• 将前驱节点的 next 指针指向要删除节点的下一个节点。
• 删除要删除的节点。

if (position === 0) {
  return head.next;
}

var cur = head;
var pre = null;
var index = 0;

while (index < position) {
  pre = cur;
  cur = cur.next;
  index++;
}

pre.next = cur.next;

return head;

链表的反转

链表的反转可以从头节点开始遍历每个节点，并将其插入到一个新的链表中。

var reverseList = function(head) {
  var newHead = null;

  while (head !== null) {
    var next = head.next;
    head.next = newHead;
    newHead = head;
    head = next;
  }

  return newHead;
};

链表的示例说明

示例一

在以下的链表中插入一个值为 4 的节点，插入的位置为 2：

1 -> 2 -> 3

插入后的结果为：

1 -> 2 -> 4 -> 3

实现代码：

var head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

function insert(head, val, position) {
  var newNode = new ListNode(val);
  if(position === 0) {
    newNode.next = head;
    return newNode;
  } 

  var cur = head;
  var pre = null;
  var index = 0;

  while(index < position) {
    pre = cur;
    cur = cur.next;
    index++;
  }

  pre.next = newNode;
  newNode.next = cur;

  return head;
}

head = insert(head, 4, 2);
// head: 1 -> 2 -> 4 -> 3

示例二

在以下的链表中删除一个值为 2 的节点：

1 -> 2 -> 3

删除后的结果为：

1 -> 3

实现代码：

var head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

function deleteNode(head, val) {
  if (head === null) {
    return head;
  }

  if (head.val === val) {
    return head.next;
  }

  var cur = head;
  var pre = null;

  while (cur !== null) {
    if (cur.val === val) {
      pre.next = cur.next;
    } else {
      pre = cur;
      cur = cur.next;
    }
  }

  return head;
}

head = deleteNode(head, 2);
// head: 1 -> 3

阅读剩余 76%