算法强化--002：链表算法题 - 《算法强化》

1. 找到链表中环的入口结点
- 1.1 哈希表
- 1.2 快慢指针
2. 删除链表的倒数第N个结点
- 2.1 计算链表长度
- 2.2 双指针
3. 链表反转
- 3.1 迭代
- 3.2 递归

1. 找到链表中环的入口结点

给定一个链表的头结点head ，返回链表开始入环的第一个结点。如果链表无环，则返回null

如果链表中有某个结点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环

注意：

pos不作为参数进行传递，仅仅是为了标识链表的实际情况
不允许修改链表

示例1：

输入：head = [3, 2, 0, -4]，pos = 1
输出：返回索引为1的链表结点
解释：链表中有一个环，其尾部连接到第二个结点

示例2：

输入：head = [1, 2]，pos = 0
输出：返回索引为0的链表结点
解释：链表中有一个环，其尾部连接到第一个结点

示例3：

输入：head = [1]，pos = -1
输出：返回null
解释：链表中没有环

1.1 哈希表

使用一个HashMap作为辅助存储空间。遍历链表时，验证结点在HashMap中是否存在

如果不存在，将结点加入HashMap中，并进入下一次循环。如果存在，该结点即为入环点

当链表遍历结束时，还没有在HashMap中找到已存在的结点，说明此链表没有环

时间复杂度：O(n)
空间复杂度：O(n)

1.2 快慢指针

使用快、慢指针作为辅助存储空间。默认将两个指针都指向首元结点，然后开始遍历链表。快指针每次走一步，慢指针每次走两步，当快、慢指针相遇时，该结点为相遇点。如果在相遇前链表遍历结束，说明此链表没有环

当快、慢指针相遇后，将快指针指向首元结点，重新开始遍历链表。让快、慢指针以相同速度，每次一步向前移动。当再次相遇时，该结点为入环点

时间复杂度：O(n)
空间复杂度：O(1)

代码实现：

class Solution {
    class ListNode {
        public var val: Int?;
        public var next: ListNode?;
        init(){}
        init(_ val: Int) {
            self.val = val
            self.next = nil
        }
    }
    fileprivate var _head : ListNode;
    private var _count : Int;
    init(list : [Int], pos : Int){
        _head = ListNode();
        _count = list.count;
        var tail = _head;
        for i in list {
            let node = ListNode(i);
            tail.next = node;
            tail = node;
        }
        tail.next = getNode(index: pos);
    }
    fileprivate func getNode(index : Int) -> ListNode? {
        if(index < 0 || index >= _count){
            return nil;
        }
        var i = 0;
        var node = _head.next;
        while(node != nil && i < index){
            node = node?.next;
            i += 1;
        }
        return node;
    }
    fileprivate var _fast : ListNode?;
    fileprivate var _slow : ListNode?;
    func detectCycle() -> ListNode? {
        _fast = _head.next;
        _slow = _head.next;
        while(_fast != nil && _fast?.next != nil && _slow != nil){
            _fast = _fast?.next?.next;
            _slow = _slow?.next;
            if(_fast?.val != _slow?.val){
                continue;
            }
            _fast = _head.next;
            while(_fast?.val != _slow?.val){
                _fast = _fast?.next;
                _slow = _slow?.next;
            }
            return _fast;
        }
        return nil;
    }
}

假设：快指针越过了慢指针，我们将当前慢指针所在位置定义为i，快指针的所在位置即为i + 1。此时慢指针的前一步为i - 1，而快指针的前一步为(i + 1) - 2 = i - 1。所以只要链表有环，快慢指针以不同速度向前移动，在某一时刻一定会相遇

基于上述原理，设链表中环外部分的长度为a，慢指针进入环后，又走了b的距离与快指针相遇。此时，快指针已经走完了环的n圈

所以，当快慢指针相遇时，快指针的移动距离为a + n(b + c) + b，慢指针的移动距离为a + b
而快指针的移动距离是慢指针的两倍，即：a + n(b + c) + b == 2(a + b)

通过公式推导，我们可以得到以下结论：a + n(b + c) + b == 2(a + b) →

a + n(b + c) + b == 2a + 2b →

n(b + c) + b == a + 2b →

a == n(b + c) + b - 2b →

a == n(b + c) + b →

a == (n - 1)b + nc →

a == (n - 1)(b + c) + c

从公式中不难发现，从相遇点到入环点的距离，再加上n − 1圈的环长，恰好等于从链表头部到入环点的距离

因此我们将快指针指向首元结点，慢指针留在相遇点的位置，此时让它们以相同的速度移动，再次相遇的点即为入环点

2. 删除链表的倒数第N个结点

给出一个链表，删除链表的倒数第n个结点，并且返回链表的头结点

示例1：

输入：head = [1, 2, 3, 4, 5]，n = 2
输出：[1, 2, 3, 5]

示例2：

输入：head = [1]，n = 1
输出：[]

示例3：

输入：head = [1, 2]，n = 1
输出：[1]

2.1 计算链表长度

我们可以通过链表的遍历，得到链表的总长度L。然后再次将链表进行遍历，当遍历到L - n个结点时，下一个结点即是待删除结点。之后只需要做一次指针的修改，即可完成删除操作

时间复杂度：O(L)
空间复杂度：O(1)

2.2 双指针

我们可以使用快、慢指针，先让快指针超过慢指针n个结点，然后让快、慢指针每次一步向前移动。当快指针移动到链表结尾时，慢指针刚好是倒数第n个结点的前驱结点

时间复杂度：O(L)
空间复杂度：O(1)

代码实现：

class Solution {
    class ListNode {
        public var val: Int?;
        public var next: ListNode?;
        init(){}
        init(_ val: Int) {
            self.val = val
            self.next = nil
        }
    }
    fileprivate var _head : ListNode;
    init(list : [Int]){
        _head = ListNode();
        var tail = _head;
        for i in list {
            let node = ListNode(i);
            tail.next = node;
            tail = node;
        }
    }
    fileprivate var _fast : ListNode?;
    fileprivate var _slow : ListNode?;
    func removeNthFromEnd(n : Int) -> ListNode? {
        if(n < 1){
            return _head.next;
        }
        // 1、快慢双指针同时指向首元结点
        _fast = _head.next;
        _slow = _head.next;
        // 2、让快指针超过慢指针n个结点
        for _ in 1 ... n {
            if(_fast == nil){
                return _head.next;
            }
            _fast = _fast?.next;
        }
        // 3、遍历链表，当快指针移动到链表结尾时停止
        while(_fast?.next != nil){
            // 让快、慢指针以相同速度，每次一步向前移动
            _slow = _slow?.next;
            _fast = _fast?.next;
        }
        // 此时，慢指针的next结点，即是待删除结点
        _slow?.next = _slow?.next?.next;
        return _head.next;
    }
}

3. 链表反转

给出单链表的头结点 head ，请反转链表，并返回反转后的链表

示例：

输入：head = [1, 2, 3, 4, 5]
输出：[5, 4, 3, 2, 1]

3.1 迭代

遍历链表时，只需要将当前结点的指针域指向前驱结点即可。改变当前结点指针域之前，需要先对其进行备份。由于单向链表无法直接找到前驱结点，可以使用一个对象进行临时存储

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
    class ListNode {
        public var val: Int?;
        public var next: ListNode?;
        init(){}
        init(_ val: Int) {
            self.val = val
            self.next = nil
        }
    }
    fileprivate var _head : ListNode;
    init(list : [Int]){
        _head = ListNode();
        var tail = _head;
        for i in list {
            let node = ListNode(i);
            tail.next = node;
            tail = node;
        }
    }
    func reverseList() {
        var curr = _head.next;
        var prev : ListNode?;
        while(curr != nil){
            let tmp = curr?.next;
            curr?.next = prev;
            prev = curr;
            curr = tmp;
        }
        _head.next = prev;
    }
}

3.2 递归

递归法的关键在于反向工作，假设链表为：

若从结点nk + 1到nm已经被反转，而我们正处于nk

我们希望nk + 1的下一个结点指向nk，所以将nk.next.next = nk，还要将nk.next = nil，否则会产生循环

时间复杂度：O(n)
空间复杂度：O(n)

代码实现：

class Solution {
    func reverseList() {
        _head.next = reverseList(curr: _head.next);
    }
    func reverseList(curr : ListNode?) -> ListNode? {
        if(curr == nil || curr?.next == nil){
            return curr;
        }
        let prev = reverseList(curr: curr?.next);
        curr?.next?.next = curr;
        curr?.next = nil;
        return prev;
    }
}