[编程题]链表中倒数第k个结点
人民的名义
Python 设置两个指针，p1，p2，先让p2走k-1步，然后再一起走，直到p2为最后一个 时，p1即为倒数第k个节点
编辑于 2019-08-13 14:41:34
回复(23)
import java.util.*;
public class LastKInLinkedList {
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public ListNode FindKthToTail(ListNode head,int k) {
if (k <= 0) {
return null;
}
if (head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
int count = 0;
while (count != k-1) {
if (fast.next != null) {
fast = fast.next;
count++;
} else {
return null;
}
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
发表于 2023-11-30 16:32:58
回复(0)
// 因为倒数第k个节点，与最后一个位置的节点相差 k-1 个元素 // 所以让 fast 先走 k-1 步，然后 fast 和 slow 同时走 // 直到 fast.next = null，即 fast 走到最后一个位置
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0)
return null;
ListNode fast = head;
ListNode slow = head;
while(k-1 > 0){
fast = fast.next;
if(fast == null)
return null;
k--;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
发表于 2023-07-02 16:05:52
回复(0)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode cur = head;
int count = 0;
while(cur!= null){ //计算节点数
count++;
cur = cur.next;
}
if(k>count){ //无效节点位置
return null;
}
for(int i = 0; i<count-k;i++ ){ //找
head = head.next;
}
return head;
}
}
发表于 2022-12-06 22:47:25
回复(0)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k < 0) {
return null;
}
ListNode first = head;
ListNode second = head;
while (k > 0 && first != null) {
k--;
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
return k > 0 ? null : second;
}
}
发表于 2022-05-24 12:08:40
回复(0)
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null){
return head;
}
if(k<=0){
return null;
}
ListNode fast=head;
ListNode show=head;
while(k-1>0){
fast=fast.next;
if(fast==null){
return null;
}
k--;
}
while(fast.next!=null){
fast=fast.next;
show=show.next;
}
return show;
}
}
发表于 2022-05-06 21:24:55
回复(0)
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null){
return null;
}
ListNode fast=head;
ListNode slow=head;
while(k!=1){
if(fast.next!=null){
fast=fast.next;
k--;
}else{
return null;
}
}//走完之后就是fast先走了k-1步
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null){
return null;
}
ListNode fast=head;
ListNode slow=head;
while(k!=1){
if(fast.next!=null){
fast=fast.next;
k--;
}else{
return null;
}
}//走完之后就是fast先走了k-1步
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
发表于 2022-01-05 12:19:34
回复(0)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode dummy = new ListNode(0);
doFind(head, k, dummy);
return dummy.next;
}
private int doFind(ListNode head, int k, ListNode dummy){
if (head == null) return 0;
int num = doFind(head.next, k, dummy) + 1;
if (num == k) {
dummy.next = head;
}
return num;
}
} 递归
发表于 2021-02-24 21:05:25
回复(0)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
for(int i = 0; i < k; i++) {
fast = fast.next;
if(fast == null) { // 一定要判断
return null; // k超出了链表长度
}
}
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
public ListNode FindKthToTail(ListNode head,int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
for(int i = 0; i < k; i++) {
fast = fast.next;
if(fast == null) { // 一定要判断
return null; // k超出了链表长度
}
}
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
发表于 2021-02-22 15:21:44
回复(0)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k==0) return null;
//快慢指针，先让快指针走k步,当快指针到达终点时慢指针的位置。
ListNode fast=head,slow=head;
int n=1;
while(fast!=null&&n<k){
fast=fast.next;
n++;
}
if(fast==null) return null;//k大于链表的元素数目
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
发表于 2021-02-03 11:20:52
回复(0)
/**
* 解题思路：使用快慢指针的思路。
*
* 快慢指针间隔k个节点，当快指针到达链表底部，则满指针到达倒数第k节点。
*
* @author freedom wang
* @date 2021-01-23 20:37:46
*/
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k == 0) {
return null;
}
// 定义快慢指针
ListNode fast = head;
ListNode slow = head;
// 让快指针领先k个节点
for (int i = 0; i < k - 1; i++) {
if (fast.next != null) {
fast = fast.next;
} else {
return null;
}
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
发表于 2021-01-23 20:48:23
回复(0)
//方法一：按照长度取相应节点
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k<=0) return null;
int count = 0;
ListNode current = head;
while(current != null) {
count++;
current = current.next;
}
if(count<k) return null;
current = head;
while(count-k!=0) {
current = current.next;
count--;
}
return current;
} //方法二：双链遍历
public ListNode FindKthToTail2(ListNode head, int k) {
if(head == null || k <= 0) return null;
ListNode infantry = head, res = head;
while(k>0) {
if(infantry == null) return null;
infantry = infantry.next;
k--;
}
while(infantry != null) {
infantry = infantry.next;
res = res.next;
}
return res;
}
发表于 2020-12-05 21:29:35
回复(0)
无敌烦这种第几第几的，i 和 k 总是算不清楚。这边建议搞个伪头结点 从 0 开始会舒服一些
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode endK=head;
ListNode end=head;
ListNode dummy=new ListNode(0);
dummy.next=head;
end=dummy;
if(head==null){
return head;
}
int i=0;
while(end.next!=null&&i<k){
i++;
end=end.next;
}
if(i<k){
return null;
}
while(end.next!=null){
end=end.next;
endK=endK.next;
}
return endK;
}
}
发表于 2020-12-01 17:17:46
回复(0)
/** * 利用栈 */ public ListNode FindKthToTail1(ListNode head, int k) { if (head == null) return null; Stack<ListNode> stack = new Stack<>(); while (head != null) { stack.push(head); head = head.next; } ListNode node = null; while (k > 0 && k <= stack.size()) { node = stack.pop(); k--; } return node; }
发表于 2020-11-19 16:43:02
回复(0)
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head,int k) { //方法1: // if(head==null||k<=0) // return null; // //1.遍历链表的长度 // int n=0; // ListNode tempNode = head; // while(tempNode!=null){ // n++; // tempNode = tempNode.next; // } // if(k>n) // return null; // //2.遍历获取第n-k+1个节点 // for(int i=0;i<n-k;i++){ // head = head.next; // } // return head; //方法2: /** * 思路： * 定义快指针和慢指针。 * 快指针先走 k-1 步，到达第 k 个节点。 * 然后两指针同时齐步走，当快指针到达末尾时，慢指针在倒数第 k 个节点上。 */ if (head == null || k <= 0) { return null; } ListNode slow = head; ListNode fast = head; for (int i = 1; i < k; i++) { if (fast.next == null) { return null; } fast = fast.next; } while (fast.next != null) { fast = fast.next; slow = slow.next; } return slow; } }
编辑于 2020-11-16 21:03:52
回复(0)
递归解法，到达null后，开始计数，在返回的时候判断计数是否达到了k，达到k，表示当前为倒数第k个节点。
public class Solution {
int n = -1;
ListNode res = null;
public void FindKthToTailRecur(ListNode head, int k){
if (head == null){
n = 0;
return;
}
FindKthToTailRecur(head.next, k);
n++;
if (n == k){
res = head;
}
}
public ListNode FindKthToTail(ListNode head,int k) {
n = -1;
FindKthToTailRecur(head, k);
return res;
}
}
发表于 2020-10-23 10:48:21
回复(0)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode node1 = head;
ListNode node2 = head;
int length = 0;
while (length < k && node2 != null) {
node2 = node2.next;
length++;
}
// 链表总长小于k
if (length < k) {
return null;
}
while (node2 != null) {
node2 = node2.next;
node1 = node1.next;
}
return node1;
}
}
public ListNode FindKthToTail(ListNode head,int k) {
ListNode node1 = head;
ListNode node2 = head;
int length = 0;
while (length < k && node2 != null) {
node2 = node2.next;
length++;
}
// 链表总长小于k
if (length < k) {
return null;
}
while (node2 != null) {
node2 = node2.next;
node1 = node1.next;
}
return node1;
}
}
发表于 2020-10-09 11:41:03
回复(0)
/**
题目描述
输入一个链表，输出该链表中倒数第k个结点。
题解：
利用双指针
*/
public ListNode FindKthToTail(ListNode head,int k) {
ListNode first = head, end = head;
while (end != null) {
if (k > 0) {
end = end.next;
k--;
}else {
first = first.next;
end = end.next;
}
}
if (k > 0) {
return null;
}
return first;
}
发表于 2020-10-04 16:17:10
回复(0)
思想：采用快慢指针，先让快指针向前移动k-1步，然后快慢指针同时移动到链表末端，慢指针所指的就是倒数第n-k个节点
/*
public class ListNode {int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0) {
return null;
}
ListNode fast = head;
ListNode slow = head;
int i = 0;
while(i != k-1) {
if(fast.next != null) {
fast = fast.next;
i++;
} else{
return null;
}
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
编辑于 2020-08-31 17:47:13
回复(0)
首先让快指针先行k步，然后让快慢指针每次同行一步，直到快指针指向空节点，慢指针就是倒数第K个节点。
public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k <= 0) {
return null;
}
ListNode slow = head;
ListNode fast = head;
for (int i = 0; i < k; i++) {
if (fast == null) {
return null;
}
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
发表于 2020-08-20 17:25:00
回复(0)
问题信息
难度：
269条回答
1771收藏
198432浏览
通过挑战的用户
-
2023-03-13 21:36:48 -
2023-03-11 17:51:25 -
2023-03-11 14:42:10
-
2023-03-11 10:07:11
-
2023-03-07 17:14:34
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
