LeetCode-剑指offer22.链表中倒数k个节点

发表于 分类于

题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例

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

返回链表 4->5.

题解

快慢指针法

  1. 准备一个快指针，从链表头开始，在链表上先走k步。
  2. 准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k。
  3. 快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k个元素的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/** 链表节点 */
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}
/** LeetCode-剑指offer22.链表中倒数k个节点 */
func getKthFromEnd(_ head: ListNode?, _ k: Int) -> ListNode? {
  var fast = head
  var slow = head
  // 快指针先行k步
  for _ in 1 ... k {
    if fast !== nil {
      fast = fast?.next
    } else {
      // 达不到k步说明链表过短，没有倒数k
      return nil
    }
  }
  // 快慢指针同步，快指针先到底，慢指针指向倒数第k个
  while fast !== nil {
    fast = fast?.next
    slow = slow?.next
  }
  return slow
}

遍历法

  1. 先遍历一次链表找到链表的长度
  2. 比较链表长度是否比小，如果比k小返回一个空节点
  3. 如果链表足够长，则我们从头节点往后遍历n-k次即可找到所求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/** 链表节点 */
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}
/** 遍历法 */
func getKthFromEnd2(_ head: ListNode?, _ k: Int) -> ListNode? {
  var n = 0
  var cur = head
  while cur !== nil {
    cur = cur?.next
    n += 1
  }
  if n < k {
    return nil
  }
  cur = head
  for _ in 0 ..< n - k {
    cur = cur?.next
  }
  return cur
}