剑指 Offer 22. 链表中倒数第k个节点 【c++/java详细题解】
1、题目
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
示例:
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。
提示:
0 <= nums.length <= 50000
0 <= 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
- 2、第二次遍历到第
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
二维码