链表中倒数第k个节点

---

题目：

题解：

1、双指针

• 解题思路：设置俩个指针，一个指向头节点pre，一个指向pre之后的距离k-1的节点cur，（因为两个遍历到cur.next为null时，也就是cur到了最后，pre正好是倒数第k个节点）返回pre即可。

• 复杂度分析：

  • 时间复杂度O(n)： N 为链表长度；总体看N-1，循环1走了k-1，循环2走了N-k
  • 空间复杂度O(1)

• 代码：

  // 双指针
  // 设置俩个指针，一个指向头节点pre，一个指向pre之后的距离k-1的节点cur，（因为两个遍历到cur.next为null时，也就是cur到了最后，pre正好是倒数第k个节点）返回pre即可。
  public class Solution {
       public ListNode getKthFromEnd(ListNode head, int k) {
  
          ListNode cur = head;
          // 遍历使得cur指向pre（目前是head）之后的距离k-1的节点，当中如果有空，说明倒数第k个节点是不存在的，直接返回null
          while (k-- > 1) {
              if (cur == null) {
                  return null;
              }
              cur = cur.next;
          }
  
          ListNode pre = head;
  
          while (cur.next != null) {
              cur = cur.next;
              pre = pre.next;
          }
  
          return pre;
      }
  }

• 只需要一个循环的代码：

  // 一个循环
  class Solution2 {
      public ListNode getKthFromEnd(ListNode head, int k) {
          ListNode slow=head,fast=head;
          int t = 0;
          while(fast!=null){
              if(t>=k) slow=slow.next;
              fast = fast.next;
              t++;
          }
          return slow;
      }
  }