剑指Offer（十四）：链表中倒数第k个结点

2017年12月1日11:08:19 8 9,702 °C

摘要

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

剑指Offer（十四）：链表中倒数第k个结点

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

效果示意图，以链表总共6个结点，求倒数第3个结点为例：

除此之外，要注意代码的鲁棒性。需要判断传入参数合法性问题。

2、代码

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) {
    	if(pListHead == NULL || k == 0){
            return NULL;
        }
        ListNode *pAhead = pListHead;
        ListNode *pBehind = pListHead;
        for(unsigned int i = 0; i < k - 1; i++){
            if(pAhead->next != NULL){
                pAhead = pAhead->next;
            }
            else{
                return NULL;
            }
        }
        while(pAhead->next != NULL){
            pAhead = pAhead->next;
            pBehind = pBehind->next;
        }
        return pBehind;
    }
};

struct ListNode {

int val;

struct ListNode *next;

ListNode(int x) :

val(x), next(NULL) {

}

};*/

class Solution {

public:

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

if(pListHead == NULL || k == 0){

return NULL;

}

ListNode *pAhead = pListHead;

ListNode *pBehind = pListHead;

for(unsigned int i = 0; i < k - 1; i++){

if(pAhead->next != NULL){

pAhead = pAhead->next;

}

else{

return NULL;

}

while(pAhead->next != NULL){

pAhead = pAhead->next;

pBehind = pBehind->next;

}

return pBehind;

}

};

Python2.7：

方法与C++一致：

# -*- 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 head == None or k == 0:
            return None
        phead = head
        pbehind = head
        for i in range(k-1):
            if phead.next == None:
                return None
            else:
                phead = phead.next
        while phead.next != None:
            phead = phead.next
            pbehind = pbehind.next
        return pbehind

# -*- 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 head == None or k == 0:

return None

phead = head

pbehind = head

for i in range(k-1):

if phead.next == None:

return None

else:

phead = phead.next

while phead.next != None:

phead = phead.next

pbehind = pbehind.next

return pbehind

用列表，开辟新空间了，不太好。

# -*- 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
        l = []
        while head:
            l.append(head)
            head = head.next
        if len(l) < k or k < 1:
            return None
        return l[-k]

# -*- 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

l = []

while head:

l.append(head)

head = head.next

if len(l) < k or k < 1:

return None

return l[-k]

微信公众号

分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。

目前评论：8 其中：访客 6 博主 2

mohican

陕西省西安市联通 1
回复 2018年9月5日下午9:04 沙发

根据例图，应该是倒数第三个结点

Jack Cui Admin 辽宁省沈阳市东北大学三舍南(研究生)
回复 2018年9月6日上午9:33 1层
@mohican 已更正，感谢~

cgzjdx

广东省肇庆市鹏博士长城宽带 2
回复 2019年2月28日上午11:56 板凳

不好意思，想问一个问题。。对于C++，pListHead是表头节点，比如一个单链表值为{1,2,3,4,5},那么表头结点之后顺序链接5个节点，每个节点的val依次为1，2，3，4，5，而不是4个节点吧？
链表这里我有点糊涂了。。
python和C++好像不一样？一个单链表值为{1,2,3,4,5}，那么python表头节点val为1，之后顺序链接4个节点，每个节点的val依次为2，3，4，5，而不是5个节点？

Jack Cui Admin 北京市联通
回复 2019年2月28日下午10:49 1层
@cgzjdx 单链表的结构是这样的1->2->3->4->5，需要一个一个访问。不能直接访问4所在节点，需要从头节点往后遍历。
我没看懂你说的意思。
- cgzjdx 广东省肇庆市鹏博士长城宽带 2
  回复 2019年3月1日上午11:03 2层
  @Jack Cui 嗯嗯，不是这个意思。。不过我已经弄清楚了，还是谢谢啦。
一书一世界 黑龙江省哈尔滨市双城区联通 2
回复 2020年7月20日下午3:08 1层
@cgzjdx 问题应该是：链表的表头有不同的写法。
（1）比如一个单链表值为{1,2,3,4,5}，1最为第一个节点（此情况也称为头节点），用一个头指针指向它。
（2）同样比如一个单链表值为{1,2,3,4,5}，1最为第一个节点（此情况它不是头节点），但是前面还一个节点做头节点（头节点里面的val，不存储任何信息，或者也可以存储链表长度信息），再用一个头指针指向这个头节点。
之前看过《大话数据结构》，里面有介绍过这种问题。

Dylan

广东省汕头市联通 1
回复 2019年3月7日下午11:29 地板

你好，这个程序是输出倒数k个节点吧？虽然牛客网可以通过

一书一世界

黑龙江省哈尔滨市双城区联通 2
回复 2020年7月20日下午3:15 4楼

本文方法挺巧妙。正常的思路：
（1）找到链表结尾，往回查找k个节点。写程序时逆向查找可能不好理解。
（2）找到链表结尾，计算链表长度，根据倒数第k个节点可以计算处正数的节点序数，也可输出（需要遍历两次链表）（3）再优化就是本文方法，遍历一次即可。学到了。

发表评论取消回复

mohican 陕西省西安市联通 1
回复 2018年9月5日下午9:04 沙发
根据例图，应该是倒数第三个结点
- Jack Cui Admin 辽宁省沈阳市东北大学三舍南(研究生)
  回复 2018年9月6日上午9:33 1层
  @mohican 已更正，感谢~
cgzjdx 广东省肇庆市鹏博士长城宽带 2
回复 2019年2月28日上午11:56 板凳
不好意思，想问一个问题。。对于C++，pListHead是表头节点，比如一个单链表值为{1,2,3,4,5},那么表头结点之后顺序链接5个节点，每个节点的val依次为1，2，3，4，5，而不是4个节点吧？
链表这里我有点糊涂了。。
python和C++好像不一样？一个单链表值为{1,2,3,4,5}，那么python表头节点val为1，之后顺序链接4个节点，每个节点的val依次为2，3，4，5，而不是5个节点？
- Jack Cui Admin 北京市联通
  回复 2019年2月28日下午10:49 1层
  @cgzjdx 单链表的结构是这样的1->2->3->4->5，需要一个一个访问。不能直接访问4所在节点，需要从头节点往后遍历。
  我没看懂你说的意思。
  - cgzjdx 广东省肇庆市鹏博士长城宽带 2
    回复 2019年3月1日上午11:03 2层
    @Jack Cui 嗯嗯，不是这个意思。。不过我已经弄清楚了，还是谢谢啦。
- 一书一世界 黑龙江省哈尔滨市双城区联通 2
  回复 2020年7月20日下午3:08 1层
  @cgzjdx 问题应该是：链表的表头有不同的写法。
  （1）比如一个单链表值为{1,2,3,4,5}，1最为第一个节点（此情况也称为头节点），用一个头指针指向它。
  （2）同样比如一个单链表值为{1,2,3,4,5}，1最为第一个节点（此情况它不是头节点），但是前面还一个节点做头节点（头节点里面的val，不存储任何信息，或者也可以存储链表长度信息），再用一个头指针指向这个头节点。
  之前看过《大话数据结构》，里面有介绍过这种问题。
Dylan 广东省汕头市联通 1
回复 2019年3月7日下午11:29 地板
你好，这个程序是输出倒数k个节点吧？虽然牛客网可以通过
一书一世界 黑龙江省哈尔滨市双城区联通 2
回复 2020年7月20日下午3:15 4楼
本文方法挺巧妙。正常的思路：
（1）找到链表结尾，往回查找k个节点。写程序时逆向查找可能不好理解。
（2）找到链表结尾，计算链表长度，根据倒数第k个节点可以计算处正数的节点序数，也可输出（需要遍历两次链表）（3）再优化就是本文方法，遍历一次即可。学到了。

一、前言

二、题目

1、思路

2、代码

发表评论取消回复

目前评论：8 其中：访客 6 博主 2

登录 注册 找回密码

登录注册找回密码