題目描述

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

思路

假設(shè)鏈表中的節(jié)點數(shù)大于等于k個，那么一定會存在倒數(shù)第k個節(jié)點，首先使用一個快指針先往前走k步，然后兩個指針每次走一步，兩個指針之間始終有k的距離，當快指針走到末尾時，慢指針所在的位置就是倒數(shù)第k個節(jié)點。

做題可能出現(xiàn)的問題

考慮k小于0的情況，其次就是鏈表的長度是否夠k個長度

python

# -*- coding:utf-8 -*-

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

def FindKthToTail(self, head, k):

# write code here

if not head or k<=0:

return None

p = q = head

count = 0

while q is not None and count

q = q.next

count += 1

if count

return None

while q is not None:

q = q.next

p = p.next

return p

C++

/*

struct ListNode {

int val;

struct ListNode *next;

ListNode(int x) :

val(x), next(NULL) {

}

};*/

class Solution {

public:

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {

ListNode *ptr1 = pListHead; // 指針１

ListNode *ptr2 = pListHead;　//指針２

if (pListHead == NULL || k == 0)//考慮全面

return NULL;

int i;

for(i=0;i

{

if(ptr1->next) // 這個條件等價于方法一種的，if(nnext==null，說明k太大了，超出了鏈表的總結(jié)點個數(shù)

ptr1 = ptr1->next;

else

return NULL;

}

while(ptr1->next)　//　p1走到end，　p2開始走

{

ptr1=ptr1->next;

ptr2=ptr2->next;

}

return ptr2;

}

};

總結(jié)

以上是生活随笔為你收集整理的python删除链表的倒数第k个节点,剑指offer 链表中的倒数第K个节点 Python and C++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。