LeetCode——剑指 Offer 22. 链表中倒数第k个节点(Java)
2021/9/2 9:06:05
本文主要是介绍LeetCode——剑指 Offer 22. 链表中倒数第k个节点(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
题干: 输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯 本题从1开始计数,即链表的尾节点是倒数第1个节点。 例如,一个链表有 6 个节点,从头节点开始 它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 示例: 给定一个链表: 1->2->3->4->5, 和 k = 2. 返回链表 4->5.
题解思路
返回链表中倒数第k个节点,关于链表首先想到的就是遍历 如果是简单的遍历,因为需要的是倒数第k个节点,所以我们有两种方法 第一种就是先将链表倒置,然后取出第k个正序的节点,不过这种显然消耗很大 第二种就是做一个标志位在第一次遍历链表的时候记录总长度,然后找到 总长度n - k的节点 这是我们采用遍历的方式,如果我们换一种思路,采用双指针的思想来写第二种方法 通常在链表问题中,双指针方法往往有奇效,这里我采用快慢指针的方法来解决
正确代码
// 顺序查找 public ListNode getKthFromEnd(ListNode head, int k) { int n = 0; ListNode node = null; for (node = head; node != null; node = node.next) { n++; } for (node = head; n > k; n--) { node = node.next; } return node; } // 双指针 public ListNode getKthFromEnd01(ListNode head, int k) { ListNode fast = head; ListNode slow = head; while (fast != null && k > 0) { fast = fast.next; k--; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; }
总结
关于链表问题,指针是非常常用的解题方法,我还依稀记得在一次面试中问我链表判断有无环的问题 当时比较紧张所以没有回答出来,其他问题倒是解决的游刃有余,现在一想就是快慢指针的解法 如果文章存在问题或者有更好的题解,欢迎在评论区斧正和评论,各自努力,你我最高处见
这篇关于LeetCode——剑指 Offer 22. 链表中倒数第k个节点(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-28中外程序员到底有啥区别?
- 2024-05-25外企也半夜发布上线吗?
- 2024-05-24鸿蒙原生应用再新丁!芒果TV 入局鸿蒙
- 2024-05-22基本概念
- 2024-05-22检索数据
- 2024-05-22排序数据
- 2024-05-22基础过滤数据
- 2024-05-22通过逻辑操作符过滤数据
- 2024-05-22通过通配符过滤数据
- 2024-05-22字段的拼接与计算