链表中倒数最后k个结点

描述

输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。

示例1

1
2


输入：{1,2,3,4,5},1 
返回值：{5}

思路

(1) 我的想法是基于链表先构建一个切片，切片对于索引的查找很便捷。

(2) 对于倒数k个结点到尾结点利用切片的特性[len(recordList) - k:]可以获取；

(3) 基于结果切片的数据构建对应该切片的链表；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// 定义链表结构
type ListNode struct {
	Val  int
	Next *ListNode
}

// 打印链表
func (l *ListNode) readLink() {
	var result []int
	for l != nil {
		result = append(result, l.Val)
		l = l.Next
	}
	fmt.Println(result)
}

其实这个思路也就是网上盛传的“数组法”, 大意是：把每个节点装进数组中，访问倒数第 k 个元素。

ps: my ugly code*

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
*/
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
    tmp := pHead
	var recordList []int
	for tmp != nil{
		recordList = append(recordList, tmp.Val)
		tmp = tmp.Next
	}

	if len(recordList) < k{
		return nil
	}

	// 基于resList构建链表
	resList := recordList[len(recordList) - k:]
	if len(resList) == 0{
		return nil
	}
	res := &ListNode{
		Val:resList[0],
	}

	temp := res
	for i:=1; i<len(resList);i++  {
		temp.Next = &ListNode{ Val:  resList[i]}
		temp = temp.Next
	}
	return res
}

测试用例

功能测试（输入的链表有多个节点，输入的链表只有一个节点）

特殊输入的测试（输入的链表头结点的指针为nil）

本题考点

考察单链表的理解和编程能力；

考察对循环，链表的遍历和查找，构建等；

高手解法与赏析

双指针法

用两个指针 left, right 指向头节点

把 right 指针后移 k 个位置

把 left, right 同时后移直到 right 到链表尾部，此时 left 指向的就是倒数第 k 个节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// c++
class Solution {
public:
 ListNode* FindKthToTail(ListNode* pHead, int k) {
     ListNode* r = pHead;
     while (k-- && r) 
         r = r->next; // 移动右侧指针造成 k 的距离差
     if (k >= 0) return nullptr; // 此时说明 k 比链表长度长
     ListNode* l = pHead;
     while (r)
         r = r->next, l = l->next; // 两个指针一起移动找到倒数第 k 个节点
     return l;
 }
};

或者给出一个Python解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


# python3
class Solution:
 def FindKthToTail(self , p , k ):
     l, r = p, p 
     while k > 0 and r:
         r = r.next
         k -= 1
     if k > 0: return None // 判断不合法的 k 值
     while r:
         l = l.next
         r = r.next
     return l

参考资料

牛客网精华题解

文章目录

链表中倒数最后k个结点

描述

示例1

思路

测试用例

本题考点

高手解法与赏析

参考资料