【揭秘前端面試】輕鬆掌握鏈表演算法通關秘籍

引言

鏈扮演算法是前端口試中罕見的高頻考點，它考察了口試者對數據構造的懂得、演算法實現才能以及對界限情況的考慮。本文將深刻剖析鏈扮演算法，幫助前端開辟者輕鬆控制這一通關秘籍。

鏈表基本

鏈表定義

鏈表是一種非線性數據構造，由一系列節點構成，每個節點包含數據域跟指針域。數據域存儲節點數據，指針域指向下一個節點。

鏈表範例

• 單向鏈表：每個節點只有一個指向下一個節點的指針。
• 雙向鏈表：每個節點有兩個指針，一個指向前一個節點，一個指向下一個節點。
• 輪回鏈表：鏈表最後一個節點的指針指向鏈表頭節點。

鏈表操縱

創建鏈表

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

總結

鏈扮演算法是前端口試中重要的知識點，控制鏈扮演算法有助於進步編程才能跟處理成績的才能。經由過程本文的講解，信賴你曾經對鏈扮演算法有了更深刻的懂得。在口試中，不只要控制演算法的道理跟實現，還要注意界限情況的處理，才幹輕鬆通關。