题目

输入一个链表,给出该链表中倒数第k个结点

思路

双指针p1和p2,p1比p2晚k个节点,然后同时后移,当p2到了末尾,则p1指向倒数第k个节点

代码

function findLastKth(list, n) {
  let p1 = p2 = list
  for(let i=0; i<n; i++) {
    if(!p2) return null
    p2 = p2.next
  }
  while(p2) {
    p2 = p2.next
    p1 = p1.next
  }
  return p1
}

class Node {
  constructor(val) {
    this.val = val
    this.next = null
  }
}

function createList(values) {
  if (values.length === 0) return null
  let head = new Node(values[0]), p = head
  for (let i = 1; i < values.length; i++) {
    p.next = new Node(values[i])
    p = p.next
  }
  return head
}

function showList(list) {
  let p = list
  let arr = []
  while (p) {
    arr.push(p.val)
    p = p.next
  }
  console.log(arr.join('->'))
}

let list = createList([1, 8, 3, 4, 5])
showList(list)
console.log( '倒数第4个节点是', findLastKth(list, 8) )