剑指 Offer 22. 链表中倒数第k个节点 【c++/java详细题解】

云惠网小编 2021年12月4日07:18:58
评论
1041字阅读3分28秒
摘要

目录1、题目2、思路3、c++代码4、java代码1、题目输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。示例:输入:nums = [1,2,3,4]输出:[1,3,2,4] 注:[3,1,2,4] 也是正确的答案之一。提示:0 <= nums.length <= 500000 <= nums[i] <= 100002、思路(链表,遍历) O(n)O(n)O(n)给定一个链表,让我们输

广告也精彩

样例:

2、思路

如样例所示,链表为1->2->3->4->5k = 2,倒数第2个节点为4,我们返回倒数第2节点的指针引用。下面我们来讲解最直观的思路。

k > n时,链表中没有该节点,我们返回NUll

目录

      • 1、题目
      • 2、思路
      • 3、c++代码
      • 4、java代码
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
int n = 0;
for(ListNode* p = head; p ; p = p->next) n++;
if(k > n) return NULL;
ListNode* p = head;
for(int i = 0; i < n - k; i++) p = p->next;
return p;
}
};

提示:

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。

给定一个链表,让我们输出该链表中倒数第k个节点(从1开始计数)。

时间复杂度分析: 链表总共遍历两次,所以时间复杂度是
O
(
n
)
O(n)
O(n)

class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
int n = 0;
for(ListNode p = head; p != null; p = p.next) n++;
if(k > n) return null;
ListNode p = head;
for(int i = 0; i < n - k; i++) p = p.next;
return p;
}
}
  • 0 <= nums.length <= 50000
  • 0 <= nums[i] <= 10000

首先我们知道单调表无法索引到前驱节点,因此我们就不能直接从后往前遍历,只能从前往后遍历。于是我们可以遍历两次,第一次遍历得到链表的总长度n,第二次遍历找到倒数第k个节点。

4、java代码

1、题目

输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。

通过画图, 我们可以直观知道链表的倒数第
k
k
k
个节点,相当于正数第
n

k
+
1
n−k+1
nk+1
个节点。

实现细节:

  • 1、第一次遍历得到链表总长度
    n
    n
    n
  • 2、第二次遍历到第
    n

    k
    +
    1
    n−k+1
    nk+1
    个节点,就是我们要找的答案。

具体过程如下:

3、c++代码

示例:

(链表,遍历)
O
(
n
)
O(n)
O(n)

原题链接:剑指 Offer 22. 链表中倒数第k个节点
在这里插入图片描述

本文转自 https://blog.csdn.net/weixin_45629285/article/details/121691926

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论