cubegao

Swift.链表中倒数第K个节点

2015-07-08

题目描述:链表中倒数第 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
30
31
32
import Foundation

class For15Solution {
func reversedK(_ head: ListNode?,_ k: Int) -> ListNode? {

guard head != nil && k != 0 else {
return nil
}

var i = 0
var p = head
var q = head

while p?.next != nil {

p = p?.next

if i >= k - 1 {
q = q?.next
}

i += 1
}

if i < k - 1 {
return nil
}

return q
}
}

算法思想:设链表的长度为 N。设置两个指针 P1 和 P2,先让 P1 移动 K 个节点,则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动,可以知道当 P1 移动到链表结尾时,P2 移动到第 N - K 个节点处,该位置就是倒数第 K 个节点。

github地址:https://github.com/cubegao/LeetCode

Tags: 算法

扫描二维码,分享此文章