链表中倒数第k个节点

发表于 | 分类于 |
字数统计: 645 字 | 阅读时长 ≈ 2 分钟

题目描述：输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例 ：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
  public ListNode getKthFromEnd(ListNode head, int k) {

  }
}

###方法一：双指针

  1. 初始化： 前指针 former 、后指针 latter ，双指针都指向头节点 head 。
  2. 构建双指针距离： 前指针 former 先向前走 k 步（结束后，双指针 former 和 latter 间相距 k 步）。
  3. 双指针共同移动： 循环中，双指针 former 和 latter 每轮都向前走一步，直至 former 走过链表 尾节点 时跳出（跳出后， latter 与尾节点距离为 k-1，即 latter 指向倒数第 k 个节点）。
  4. 返回值： 返回 latter 即可。
img 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
  public ListNode getKthFromEnd(ListNode head, int k) {
    if(head == null || k == 0) return null;
    ListNode former = head, latter = head;
    for(int i = 0; i < k; i++) {
      former = former.next;
    }
    while(former != null) {
      latter = latter.next;
      former = former.next;
    }
    return latter;
  }
}

复杂度分析：
时间复杂度：O(N)，N 为链表长度；总体看， former 走了 N 步， latter 走了 (N-k) 步
空间复杂度：O(1)，双指针 former , latter 使用常数大小的额外空间

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
  • 内存消耗：37.6 MB, 在所有 Java 提交中击败了71.45%的用户

方法二：栈

把链表的节点都推到栈中，利用栈 先进后出 的特点，把所需节点弹出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
  public ListNode getKthFromEnd(ListNode head, int k) {
    if(head == null || k == 0) return null;
    Deque<ListNode> stack = new LinkedList<ListNode>();
    ListNode temp = head;
    while(temp != null) {
      stack.push(temp);
      temp = temp.next;
    }
    ListNode res = null;
    while(k != 0) {
      res = stack.pop();
      k--;
    }
    return res;
  }
}

复杂性分析：

  • 时间复杂度：O(n)。正向遍历一遍链表 n，再在栈中弹出相应节点 k
  • 空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点

执行结果：通过

执行用时：1 ms, 在所有 Java 提交中击败了14.73%的用户

内存消耗：37.8 MB, 在所有 Java 提交中击败了36.30%的用户