【Offer】[22] 【链表中倒数第k个结点】
2024-09-01 06:20:45
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路分析
- 采用双指针的方法，第一个指针首先向前移动k-1个位置，第二个指针指向头节点，然后将两个指针同时向后移动，如果第一个指针走到链表尾结点时，第二个指针的位置就正好为 倒数第k个节点
测试用例
- 功能测试：第k个节点在链表的中间;第k个节点是链表的头节点;第k个节点是链表的尾节点。
- 特殊输入测试：链表头节点为nullptr指针:链表的节点总数少于k;k等于0。
Java代码
public class Offer22 {
public static void main(String[] args) {
test1();
test2();
test3();
test4();
}
public static ListNode FindKthToTail(ListNode head, int k) {
return Solution1(head, k);
}
/**
* 双指针的方法
* @param head
* @param k
* @return
*/
private static ListNode Solution1(ListNode head, int k) {
if (head == null || k == 0) {
return null;
}
ListNode pBefore = head;
ListNode pBeHind = null;
for (int i = 0; i < k - 1; i++) {
if (pBefore.next != null) {
pBefore = pBefore.next;
} else {
return null;
}
}
pBeHind = head;
while (pBefore.next != null) {
pBefore = pBefore.next;
pBeHind = pBeHind.next;
}
return pBeHind;
}
private static void test1() {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
head.next = node2;
node2.next = node3;
node3.next = node4;
ListNode kthNode = FindKthToTail(head, 4);
System.out.println("{1,2,3,4},4 ---> " + kthNode.val);
}
private static void test2() {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
head.next = node2;
node2.next = node3;
node3.next = node4;
ListNode kthNode = FindKthToTail(head, 5);
if (kthNode == null) {
System.out.println("{1,2,3,4},5---> null ");
} else {
System.out.println("测试失败！");
}
}
private static void test3() {
ListNode head = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
head.next = node2;
node2.next = node3;
node3.next = node4;
ListNode kthNode = FindKthToTail(head, 0);
if (kthNode == null) {
System.out.println("{1,2,3,4},0---> null ");
} else {
System.out.println("测试失败！");
}
}
private static void test4() {
ListNode head = null;
ListNode kthNode = FindKthToTail(head, 4);
if (kthNode == null) {
System.out.println("{null},4---> null ");
} else {
System.out.println("测试失败！");
}
}
}
代码链接
最新文章
- java 内部类与外部类的区别
- HDFS的Shell
- ECharts地图中tooltip提示框通过formatter分别显示多个数值
- mybatis系列-05-SqlMapConfig.xml详解
- UNIX标准化及实现之基本系统数据类型
- repo manifest xml 文件修改后提交命令
- 取出当前会话的sid等
- python unicodeDecode error
- jq分页插件，支持动态，静态分页的插件，简单易用。
- 自动刷新 CSS文件
- HP DL380服务器RAID信息丢失数据恢复方法和数据恢复过程分享
- python3 集合 操作方法
- linux的软件安装方式总结
- "人机"对战：电脑太简单了，我是射手 skr~skr~skr
- 【安卓进阶】Scroller理解与应用
- Hexo NexT 博客本地搭建指南
- PHP 生成唯一的激活码
- 使用AdBlock plus屏蔽广告
- CodeForces 814D An overnight dance in discotheque（贪心+dfs）
- 如何在openwrt上实现 U盘的自动挂载