剑指Offer22链表中倒数第k个节点 [复制链接]

目录

1、题目2、思路、c++代码4、java代码

1、题目

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

示例：

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

提示：

0=nums.length==nums=

2、思路

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

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

样例：

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

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

通过画图，我们可以直观知道链表的倒数第kkk个节点，相当于正数第nk+1nk+1nk+1个节点。

具体过程如下：

1、第一次遍历得到链表总长度nnn。2、第二次遍历到第nk+1nk+1nk+1个节点，就是我们要找的答案。

实现细节：

当kn时，链表中没有该节点，我们返回NUll。

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

、c++代码

classSolution{publicistNode*getKthFromEnd(ListNode*head,intk){intn=0;for(ListNode*p=head;p;p=p-next)n++;if(kn)turnNULL;ListNode*p=head;for(inti=0;in-k;i++)p=p-next;turnp;}};

4、java代码

classSolution{publicListNodegetKthFromEnd(ListNodehead,intk){intn=0;for(ListNodep=head;p!=null;p=p.next)n++;if(kn)turnnull;ListNodep=head;for(inti=0;in-k;i++)p=p.next;turnp;}}

原题链接：剑指Offer22.链表中倒数第k个节点

,