剑指 Offer 22. 链表中倒数第k个节点 【c++/java详细题解】
1、题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
0 <= nums.length <= 500000 <= nums[i] <= 10000
2、思路
(链表，遍历)
O
(
n
)
O(n)
O(n)
给定一个链表，让我们输出该链表中倒数第k个节点（从1开始计数）。
样例：
如样例所示，链表为1->2->3->4->5，k = 2，倒数第2个节点为4，我们返回倒数第2节点的指针引用。下面我们来讲解最直观的思路。
首先我们知道单调表无法索引到前驱节点，因此我们就不能直接从后往前遍历，只能从前往后遍历。于是我们可以遍历两次，第一次遍历得到链表的总长度n，第二次遍历找到倒数第k个节点。
通过画图， 我们可以直观知道链表的倒数第
k
k
k 个节点，相当于正数第
n
−
k
+
1
n−k+1
n−k+1 个节点。
具体过程如下：
- 1、第一次遍历得到链表总长度
n
n
n。 - 2、第二次遍历到第
n
−
k
+
1
n−k+1
n−k+1 个节点，就是我们要找的答案。
实现细节：
当k > n时，链表中没有该节点，我们返回NUll。
时间复杂度分析： 链表总共遍历两次，所以时间复杂度是
O
(
n
)
O(n)
O(n)。
3、c++代码
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;
}
};
4、java代码
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;
}
}
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
二维码