【揭秘前端面试】轻松掌握链表算法通关秘籍

引言

链表算法是前端面试中常见的高频考点，它考察了面试者对数据结构的理解、算法实现能力以及对边界情况的考虑。本文将深入解析链表算法，帮助前端开发者轻松掌握这一通关秘籍。

链表基础

链表定义

链表是一种非线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。数据域存储节点数据，指针域指向下一个节点。

链表类型

• 单向链表：每个节点只有一个指向下一个节点的指针。
• 双向链表：每个节点有两个指针，一个指向前一个节点，一个指向下一个节点。
• 循环链表：链表最后一个节点的指针指向链表头节点。

链表操作

创建链表

function createLinkedList(data) {
  let head = new ListNode(data[0]);
  let current = head;
  for (let i = 1; i < data.length; i++) {
    current.next = new ListNode(data[i]);
    current = current.next;
  }
  return head;
}

插入节点

function insertNode(head, value, position) {
  let newNode = new ListNode(value);
  if (position === 0) {
    newNode.next = head;
    return newNode;
  }
  let current = head;
  let prev = null;
  let index = 0;
  while (current && index < position) {
    prev = current;
    current = current.next;
    index++;
  }
  prev.next = newNode;
  newNode.next = current;
  return head;
}

删除节点

function deleteNode(head, position) {
  if (position === 0) {
    return head.next;
  }
  let current = head;
  let prev = null;
  let index = 0;
  while (current && index < position) {
    prev = current;
    current = current.next;
    index++;
  }
  if (current) {
    prev.next = current.next;
  }
  return head;
}

反转链表

function reverseLinkedList(head) {
  let prev = null;
  let current = head;
  let next = null;
  while (current) {
    next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

常见面试题

删除链表的倒数第N个节点

function removeNthFromEnd(head, n) {
  let dummy = new ListNode(0);
  dummy.next = head;
  let fast = dummy, slow = dummy;
  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}

合并两个有序链表

function mergeTwoLists(l1, l2) {
  let dummy = new ListNode(0);
  let current = dummy;
  while (l1 && l2) {
    if (l1.val < l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }
  current.next = l1 || l2;
  return dummy.next;
}

相交链表

function getIntersectionNode(headA, headB) {
  let lenA = getLength(headA);
  let lenB = getLength(headB);
  let currentA = headA, currentB = headB;
  if (lenA > lenB) {
    for (let i = 0; i < lenA - lenB; i++) {
      currentA = currentA.next;
    }
  } else {
    for (let i = 0; i < lenB - lenA; i++) {
      currentB = currentB.next;
    }
  }
  while (currentA && currentB) {
    if (currentA === currentB) {
      return currentA;
    }
    currentA = currentA.next;
    currentB = currentB.next;
  }
  return null;
}

function getLength(head) {
  let len = 0;
  while (head) {
    len++;
    head = head.next;
  }
  return len;
}

总结

链表算法是前端面试中重要的知识点，掌握链表算法有助于提高编程能力和解决问题的能力。通过本文的讲解，相信你已经对链表算法有了更深入的了解。在面试中，不仅要掌握算法的原理和实现，还要注意边界情况的处理，才能轻松通关。