剑指Offer - 14 - 链表中倒数第k个结点

题目描述

链表中倒数第k个结点

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

思路

准备两个指针,第一个指向头,让第二个先往后走k步,之后再同时走,当第二个指针到达尾部时第一个指针指向的刚好就是倒数第k个节点

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
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容