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

引言

链表算法是前端口试中罕见的高频考点，它考察了口试者对数据构造的懂得、算法实现才能以及对界限情况的考虑。本文将深刻剖析链表算法，帮助前端开辟者轻松控制这一通关秘籍。

链表基本

链表定义

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

链表范例

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

链表操纵

创建链表

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;
}

总结

链表算法是前端口试中重要的知识点，控制链表算法有助于进步编程才能跟处理成绩的才能。经由过程本文的讲解，信赖你曾经对链表算法有了更深刻的懂得。在口试中，不只要控制算法的道理跟实现，还要留神界限情况的处理，才干轻松通关。