寻找倒数第K个节点

这篇文章也是凑数的 ...

寻找倒数第K个节点

描述 :

找出单向链表中倒数第 k 个节点。返回该节点的值。

题目 :

LeetCode 返回倒数第K个节点 : 

面试题 02.02. 返回倒数第 k 个节点

 说明 : 给定的 k 保证是有效的。

分析 :

我们给出个例子 :

首先，我们创建两个指针p1和p2，p1指向链表的头节点，p2指向链表的正数第k个节点（也就是例子中的第3个节点）：

此时，由于p2指向链表的尾节点，且p1和p2的距离是k-1，因此p1所指的节点就是我们要寻找的链表倒数第k个节点：

显然，这个方法从头到尾只需要对链表做一次遍历，而且仅仅使用了两个指针，算法的空间复杂度是O(1)。

解析 :

LeetCode

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* } */
//LeetCode
class Solution {public int kthToLast(ListNode head, int k) {ListNode newNode = new ListNode(-100);newNode.next = head;ListNode slow = newNode;ListNode fast = newNode;for(int i = 0 ;i < k ;i++){fast = fast.next;}while(fast != null){slow = slow.next;fast = fast.next;}return slow.val;}
}