链表常见面试题

下面这些代码题经常会出现在中高级前端的面试场景中，因为前端还是以UI、UX为主，所以不会问得太深，基本上把理论知识和这些代码题记一下，遇到链表类的面试题就可以比较轻松的实现了。

给定数组，构造链表

function createHead(array) {
  let head = {
    val: array[0],
    next: null
  }
  let p = head
  for(let i = 1; i < array.length; i++) {
    let obj = {
      val: array[i],
      next: null
    }
    p.next = obj
    p = p.next
  }
  return head
}

给定数组，构造循环链表

function createLoopHead(array) {
  let head = {
    val: array[0],
    next: null
  }
  let pFirst = head
  let p = head
  for(let i = 1; i < array.length; i++) {
    let obj = {
      val: array[i],
      next: null
    }
    p.next = obj
    p = p.next
    if (i === array.length - 1) {
      p.next.next = pFirst
    }
  }
  return head
}

反转链表

//方法一
function reverse(head) {
  if(head === null || head.next === null) {
    return head
  }
  let newHead = reverse(head.next)
  head.next.next = head
  head.next = null

  return newHead
}

//方法二
function reverse2(head) {
  let pre = null
  let next = null

  while(head) {
    next = head.next
    head.next = pre
    pre = head
    head = next
  }
  return pre
}

链表合并(有序链表)

//方法一
function Merge(l1, l2) {
  if(l1 === null || l2 === null) {
    return l1 || l2
  }
  if(l1.val < l2.val) {
    l1.next = Merge(l1.next, l2)
    return l1
  } else {
    l2.next = Merge(l1, l2.next)
    return l2
  }
}

//方法二
function Merge2(l1,l2) {
  let head = {
    val: 0,
    next: null
  }
  let p = head

  while(l1 && l2) {
    if(l1.val < l2.val) {
      p.next = l1
      l1 = l1.next
    } else {
      p.next = l2
      l2 = l2.next
    }
    p = p.next
  }
  p.next = l1 || l2

  return head.next
}

链表合并(无序链表)

function Merge(l1, l2) {
  let head = {
    val: 0,
    next: null
  }
  let p = head
  while(l1) {
    p.next = l1
    l1 = l1.next
    p = p.next
  }
  p.next = l2
  return head.next
}

查找链表中间位置

function middle(head) {
  let fast = head
  let slow = head

  while(fast.next && fast.next.next) {
    fast = fast.next.next
    slow = slow.next
  }
  return slow
}

判断链表是否有环，有环返回相遇结点

function isLoop(head) {
  if(head.next === null) {
    return false
  }

  let fastNode = head
  let slowNode = head
  while(fastNode.next && fastNode.next.next && slowNode !== fastNode) {
    slowNode = slowNode.next
    fastNode = fastNode.next.next
  }
  if(slowNode === fastNode) {
    return true
  }
  return false
}

返回链表倒数第K个node

function findK(head, k) {
  let p = head
  let q = p
  for(let i = 0; i < k; i++) {
    if (q === null) {
      return -1
    }
    q = q.next
  }

  while(q) {
    q = q.next
    p = p.next
  }
  return p
}

删除链表指定node

function deleteNode(head, k) {
  let p = head
  let j = 1

  while(p.next && j < k - 1) {
    p = p.next
    j++
  }
  let tmp = p.next
  p.next = tmp.next
  return head
}

链表排序

function sort(head) {
  let cur = null, tail = null
  cur = head
  while(cur.next !== tail) {
    while(cur.next !== tail) {
      if(cur.val > cur.next.val) {
        let tmp = cur.val
        cur.val = cur.next.val
        cur.next.val = tmp
      }
      cur = cur.next
    }
    tail = cur
    cur = head
  }
  return head
}