剑指offer-14、链表中倒数第k个结点
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个链表，输出该链表中倒数第k个结点。</p>
<p>例如输⼊{1,2,3,4,5} , 2 时，对应的链表结构如下图所示：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231824385.png" alt="" loading="lazy"></p>
<p>其中蓝⾊部分为该链表的最后2 个结点，所以返回倒数第2 个结点（也即结点值为4 的结点）即可，系统会打印后⾯所有的节点来⽐较。</p>
<p>示例1<br>
输⼊：{1,2,3,4,5},2<br>
返回值：{4,5}<br>
说明：返回倒数第2个节点4，系统会打印后⾯所有的节点来⽐较。</p>
<p>示例2<br>
输⼊：{2},8<br>
返回值：{}</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="两次遍历法">两次遍历法</h3>
<ol>
<li>第一次遍历计算链表长度n</li>
<li>第二次遍历到第n-K+1个节点（即倒数第K个节点）</li>
<li>如果K大于链表长度，返回null</li>
</ol>
<pre><code class="language-java">public ListNode findKthToTail(ListNode head, int k) {
if (head == null || k <= 0) return null;
// 第一次遍历计算链表长度
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// 检查k是否有效
if (k > length) return null;
// 第二次遍历找到目标节点
current = head;
for (int i = 0; i < length - k; i++) {
current = current.next;
}
return current;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要遍历链表两次</li>
<li><strong>空间复杂度</strong>：O(1)，只使用了固定数量的指针</li>
</ul>
<h3 id="双指针法推荐">双指针法（推荐）</h3>
<p>快慢双指针，先让第1 个指针先⾛k 步，然后第2 个指针开始⾛，⽽且两个指针⼀起⾛，直到第⼀个指针⾛到最后的位置。</p>
<ol>
<li>使用快慢两个指针，快指针先移动K步</li>
<li>然后两个指针同步移动，当快指针到达末尾时，慢指针正好指向倒数第K个节点</li>
<li>如果快指针在移动K步前到达末尾，说明K大于链表长度</li>
</ol>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231826585.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503231826604.png" alt="" loading="lazy"></p>
<pre><code class="language-java">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; i++) {
if (fast == null) return null; // k大于链表长度
fast = fast.next;
}
// 同步移动两个指针
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，只需遍历链表一次</li>
<li><strong>空间复杂度</strong>：O(1)，使用了两个指针</li>
</ul>
<h3 id="栈辅助法空间换时间">栈辅助法（空间换时间）</h3>
<ol>
<li>将所有节点压入栈</li>
<li>弹出K个节点，最后一个弹出的即为所求</li>
<li>如果栈中节点不足K个，返回null</li>
</ol>
<pre><code class="language-java">public ListNode findKthToTail(ListNode head, int k) {
if (head == null || k <= 0) return null;
Stack<ListNode> stack = new Stack<>();
ListNode current = head;
// 所有节点入栈
while (current != null) {
stack.push(current);
current = current.next;
}
// 检查k是否有效
if (k > stack.size()) return null;
// 弹出k个节点
ListNode result = null;
for (int i = 0; i < k; i++) {
result = stack.pop();
}
return result;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要遍历链表两次（入栈和出栈）</li>
<li><strong>空间复杂度</strong>：O(n)，需要额外栈空间存储所有节点</li>
</ul>
<h3 id="递归回溯法">递归回溯法</h3>
<ol>
<li>递归遍历到链表末尾</li>
<li>回溯时计数，当计数等于K时返回当前节点</li>
<li>使用全局变量或包装类传递计数</li>
</ol>
<pre><code class="language-java">private int count = 0;
public ListNode findKthToTail(ListNode head, int k) {
if (head == null) return null;
ListNode node = getKthFromEnd(head.next, k);
count++;
if (count == k) {
return head;
}
return node;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要完整遍历链表</li>
<li><strong>空间复杂度</strong>：O(n)，递归栈空间开销</li>
</ul>
<h3 id="方法对比与总结">方法对比与总结</h3>
<table>
<thead>
<tr>
<th>方法</th>
<th>时间复杂度</th>
<th>空间复杂度</th>
<th>优点</th>
<th>缺点</th>
</tr>
</thead>
<tbody>
<tr>
<td>两次遍历法</td>
<td>O(n)</td>
<td>O(1)</td>
<td>实现简单</td>
<td>需要两次遍历</td>
</tr>
<tr>
<td>双指针法</td>
<td>O(n)</td>
<td>O(1)</td>
<td>一次遍历，效率高</td>
<td>边界条件需仔细处理</td>
</tr>
<tr>
<td>栈辅助法</td>
<td>O(n)</td>
<td>O(n)</td>
<td>实现直观</td>
<td>空间开销大</td>
</tr>
<tr>
<td>递归回溯法</td>
<td>O(n)</td>
<td>O(n)</td>
<td>展示递归思想</td>
<td>空间效率低</td>
</tr>
</tbody>
</table>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/18992765
頁:
[1]