一、链表

链表是由一组在内存中不必相连（不必相连：可以连续也可以不连续）的内存结构Node，按特定的顺序链接在一起的抽象数据类型。

我们常见的链表结构有单链表和双向链表。

单链表，保存了下一个结点的指针，可以根据下一结点指针向下遍历

双向链表，保存了向上一个结点和向下一个结点的指针，所以可以向上下两个方向遍历。

单链表结构一般如下：

template<typename T>
struct Node
{T data; //数据Node* next; //指向下一个结点的指针
};

双向链表的结构一般如下：

template<typename T>
struct Node
{T data; //数据Node* previous; //指向上一个结点的指针Node* next; //指向下一个结点的指针
};

在算法中，我们遇到的链表题目一般可以使用一些经典的思路求解。本篇博客主要讨论这些经典的链表解题思路之一，快慢指针。

二、快慢指针

快慢指针也称龟兔赛跑算法，又叫判圈算法。具体方法是声明两个指针fast 指针和slow 指针，这两个指针按照题目的需求有不同的行进方案（例如fast每次行进2步，slow每次行进1步），但基本上步长是不同的，所以叫龟兔赛跑算法。

比较经典的题目如下，判断链表是否有环，所以又叫判圈算法。

【题目】环形链表

判断一个单链表是否有环，并且返回第一个入环节点。

一个单链表有环，即如下形式，图中第一个入环节点为2

<算法简述>

使用快慢指针求解这个问题。我们使fast和slow同时从头结点出发，同频行进。

其中fast每次走2个结点，slow每次走一个结点。

如果fast或 slow能够为nullptr，则链表无环，如果fast和slow相遇，则链表有环。

这里很容易比较得出快慢指针的一个特点1：可以判圈

使slow指针在原地（相遇位置）保持不动，并使fast指针返回头节点处，二者同频出发，每次均走一步。则再次相遇的节点为第一个入环节点。

<C++代码实现>

ListNode* hasCycle(ListNode* head)
{ListNode* fast = head;ListNode* slow = head;//判断是否有环while (nullptr != fast && nullptr != slow){if (nullptr == fast->next) return nullptr;fast = fast->next->next;slow = slow->next;//无环，返回空指针if (nullptr == fast || nullptr == slow){return nullptr;}if (fast == slow){break;}}//快指针回到头结点，快慢指针每次均走一步，相遇节点为第一个入环节点fast = head;while (nullptr != slow){if (fast == slow){break;}fast = fast->next;slow = slow->next;}return slow;
}

<复杂度分析>

时间复杂度为O(N)，额外空间复杂度为O(1)。

【题目】判断一个单链表是否是回文结构

回文结构：正向遍历和反向遍历每个结点都是相同数据的结构。例如1->2->1，1->2->2->1都是回文结构。

【方法一】使用栈结构（对照组）

想到判断回文结构，我们可以想到栈结构，因为栈是符合先入后出的数据结构，所以只要我们先遍历一遍链表，对数据进行压栈。再依次弹出栈顶，就会得到链表的反向输出。这样可以同时取到原链表的正向输出和反向输出，一一比较之后，就可以判断是否回文。

<C++代码实现>

bool isPalindrome(Node* hd)
{stack<int> st;Node* temp = hd;while (nullptr != temp){st.push(temp->data);temp = temp->next;}temp = hd;while (nullptr != temp){if (temp ->data != st.top()){return false;}temp = temp->next;st.pop();}return true;
}

<复杂度分析>

上述额外使用栈结构，所以额外空间复杂度为O(N)，时间复杂度为O(N)。

【方法二】快慢指针方法

分析：这个题目一般想不到使用快慢指针方法，但是快慢指针具有一个和此题吻合的特点2：利用快慢指针的不同步数，可以找到链表的中点。如果此题找到中点，我们也可以镜像地比较中点左右的元素，得出是否是回文结构的结论。

而使用下列方法，可以使额外空间复杂度为O(1)，这就是这个算法的优势。

bool isPalindrome(Node* hd)
{if (nullptr == hd){return true;}Node* fast = hd->next;Node* slow = hd;//快慢指针同时遍历，快指针每次走2步，慢指针每次走1步//当快指针到终点的时候，慢指针正好处于中点位置while (nullptr != fast && nullptr != fast->next){fast = fast->next->next;slow = slow->next;}//慢指针继续往下遍历，遍历的同时将指向反向Node *temp1 = slow; //temp1用于记录slow的前一个结点，用于逆序链表的后半部分Node *temp2 = slow->next; //temp1用于记录slow的后一个结点，放在链表断开后指针丢失Node *mid = slow;   //保存中点结点，便于后续使用while (nullptr != slow){slow->next = temp1;temp1 = slow;slow = temp2;if (nullptr != slow){temp2 = slow->next;}}//此时temp1为原链表终点结点,使temp2指向头结点，同时遍历temp1,temp2比较数值Node *ed = temp1; //保存终点结点，便于后续还原链表temp2 = hd;bool ret = true; //是否是回文结构while (temp1 != mid){if (temp1->data != temp2->data){ret = false;break;}temp1 = temp1->next;temp2 = temp2->next;}//从终点开始，还原原链表temp1 = ed->next;ed->next = nullptr;while (mid != ed){temp2 = ed;ed = temp1;temp1 = ed->next;ed->next = temp2;}return ret;
}

<复杂度分析>

可见此算法的coding复杂很多，但是额外空间复杂度可以做到O(1)，时间复杂度为O(N)。

【题目】删除链表的倒数第 N 个结点

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

<分析>

此题的重点难点是：如何找到倒数第N个结点。

做完上面的判断回文结构的题，我们认识到快慢指针的特点2，应该可以很容易想到：我们使fast先走N个结点，再让slow和fast同频同步行进，当fast为最后一个结点的时候，slow所在结点即为倒数第N个结点。

<C++代码实现>

ListNode* removeNthFromEnd(ListNode* head, int n)
{ListNode* fast = head;ListNode* slow = head;//fast指针先走n步while (nullptr != fast && --n > 0){fast = fast->next;}//如果链表长度小于n，则直接返回头指针if (nullptr == fast){return head;}//如果倒数第n个就是头节点，则换头节点if (nullptr == fast->next){head = head->next;delete slow;return head;}//fast和slow都前进，fast走到倒数第一个，则删除slow->next节点while (nullptr != fast->next->next){slow = slow->next;fast = fast->next;}fast = slow->next;slow->next = slow->next->next;delete fast;return head;
}