Tino又想吃肉了

找出链表的倒数第N个结点

Note swift algorithm leetcode 双指针
Word count: 211Reading time: 1 min
2021/09/01

快慢指针的一个应用
系统复习系列

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？

显然，当我们使用两个指针，慢指针从头开始遍历，每次遍历向前一个结点，快指针每次遍历向前N个结点，我们就可以在遍历结束时找到需要删除的那个结点。

以下为代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        if (head == nil || head?.next == nil) {
            return nil
        }
        var left = head
        var right = head
        for _ in 0..<n {
            right = right?.next
        }
        if right == nil {
            return head?.next
        }
        while (right?.next != nil) {
            left = left?.next
            right = right?.next
        }

        left?.next = left?.next?.next
        return head
    }
}
CATALOG
Total : 35
2022
2021
swift iOS Tools algorithm leetcode tree 动态规划 计网 DFS算法 双指针 排序 BFS 性能优化 底层原理 操作系统 启动流程
Note