Linked List

链表是重要的线性数据结构,链表的插入和删除操作具有O(1)的时间复杂度。但是链表不具有随机访问的能力,这一点给链表类问题带来了不少麻烦。另外,单向链表无法直接访问前驱节点,这也是链表的一大难点。
解决链表类问题首先需要熟悉链表的基本操作,包括创建、插入、删除、查找等。在此基础上实现链表的逆序,合并等操作。

双指针方法

链表问题中的一个重要的方法叫双指针法。定义两个指针,一个叫慢指针,另一个叫快指针。通常慢指针每次向前移动一个节点,而快指针每次向前移动若干个节点。这个方法通常用于寻找链表中特定的位置。比如找到链表的中点,可以让快指针每次移动两个节点。这样当快指针到达链表末尾时,慢指针刚好在链表中间的位置。