算法学习 - 链表

数据结构

数据结构的存储方式只有两种：数组和链表，两种都属于线性表。

数组

• 数组是顺序存储的线性表，所有元素的内存地址是连续的；
• 数组的容量是在初始化时被限定的，所以扩容需要将当前数组内容复制过去，时间复杂度为 O(n)；
• 数组可以通过索引直接获取到对应元素，时间复杂度为 O(1)；
• 数组的插入和删除同样需要后移或者前移整个数组，时间复杂度为 O(n)；

链表

• 链表也是一种线性表，但是内存地址是不连续的；
• 数组是通过指针访问下一元素，所以不存在扩容问题，时间复杂度为 O(1)；
• 链表的不连续性导致无法通过索引获取到对应的元素，无法进行随机访问，时间复杂度为 O(n)；
• 链表通过操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)；

总结

可以参考 LeetCode 教程里面的一张图：

• 如果你需要经常添加或删除结点，链表可能是一个不错的选择。
• 如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

关于链表

设计链表

链表的形式有很多，单链表、双链表、单向循环链表、双向循环链表。

我们看下单链表和双链表的数据结构，双链表比单链表多了一个 prev 指针，用来指向当前节点的前一节点，具体的实现可以参考 Design Linked List。

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class ListNode {
    public var val: Int
    public var prev: ListNode?
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.prev = nil
        self.next = nil
    }
}

反转链表

这是一道经典的题目，而且在链表里面有着广泛的应用，题目和解答直接参考 Reverse Linked List，下面再做一下详解。

外部空间

不考虑空间复杂度的情况下，完全可以使用数组或者新链表来通过外部空间进行翻转。

遍历链表将值放到数组中，数组逆序输出新链表即可，这样的话不满足 O(1) 的空间复杂度。

迭代

迭代的思路是通过双指针来实现的，我们可以看下面的思路：

• 定义双指针，pre & cur ，初始值分别为 nil & head；
• 循环条件 cur != nil，每次让 t = cur.next；
• 然后 pre 和 cur 分别后移一位直到循环结束；

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        var pre: ListNode? = nil
        var cur = head
        while cur != nil {
            let t = cur?.next
            cur?.next = pre
            pre = cur
            cur = t
        }
        return pre
    }
}

递归

递归的精髓在于将next当做参数传入reverseList函数时，在下一次递归中对参数的操作，会反应在上次的参数值上。
还是以1->2->3->4举例子，4次递归后（回溯前），其实是将引用链全部打破：

class Solution {
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        let cur = reverseList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return cur
    }
}

环形链表

这是一道经典的链表题目 - 环形链表，基本的解题思路是双指针技巧里面的快慢指针。题目和解答直接参考 Linked List Cycle。

在环形列表里面快慢指针的作用是 一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

同样的，如果是一个非环形链表，快慢指针的作用是 当快指针移动到末尾的时候，和慢指针之间的距离一定是二分之一的链表的长度，即慢指针一定回到链表的第一半的最后一个元素。

func endOfFirstHalf(_ head: ListNode?) -> ListNode? {
    var fast = head
    var slow = head
    while(slow?.next != nil && fast?.next?.next != nil) {
        fast = fast?.next?.next
        slow = slow?.next
    }
    return slow
}

回文链表

上述两个经典题应用在同一题即 Palindrome Linked List，看看能不能把这题写出来？

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/03/13/Algorithm_LinkedList/