題目描述

鏈表中倒數(shù)第k個結(jié)點

輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。

思路

準(zhǔn)備兩個指針，第一個指向頭，讓第二個先往后走k步，之后再同時走，當(dāng)?shù)诙€指針到達(dá)尾部時第一個指針指向的剛好就是倒數(shù)第k個節(jié)點

Code

• Python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
      if head is None:
        return None
      p, q = head, head
      while k > 1 and q.next is not None:
        q = q.next
        k -= 1
      if k > 1 or k == 0:
        return None
      while q.next is not None:
        p = p.next
        q = q.next
      return p

• JavaScript

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindKthToTail(head, k)
{
  if (!head) return null
  let p = head, q = head
  while(k-- > 1 && q.next) q = q.next
  if (k) return null
  while(q.next) {
    p = p.next
    q = q.next
  }
  return p
}