算法导论总结（二）链表

LeetCode刷了一百多道题，决定来发小小的总结。这篇博客主要对LeetCode中链表标签下的题目进行总结，linked-list标签下总共有27道题，这些题目较为全面的考察链表操作：插入、删除、反转、交换、合并、环路检查等。

使用哑节点

哑节点就是第一个没有用的辅助节点，可以使遍历链表的代码更加优雅（具体来说就是不需要对第一个节点做特殊处理）。

例如我们创建一个链表：

ListNode* BuildList(vector<int>& nums){
	ListNode dummy = ListNode(0);
	ListNode *head = &dummy;
	for (auto v : nums){
		head->next = new ListNode(v);
		head = head->next;
	}
	return dummy.next;
}

dummy就是哑节点， return dummy.next; 在很多情况下可以解决极端情况处理的问题 。

头插法与尾插法

头插法与尾插法不仅是重要的创建链表的方法，尤其是在要求不改变结点值的情况下，可以使用头插法来反转链表。

头插法：就是按照节点逆序方法逐渐将节点插入到链表的头部，最后产生的链表是逆序的。

尾插法：就是按照节点顺序方法将节点插入到链表的尾部，比头插法复杂两点：一是开始时需要创建第一节点，二是结束时需要将尾部指针指向NULL。

快慢指针法

快慢指针法有两个作用，第一个作用是找到链表的中间位置，第二个作用是找到链表中存在的闭合环路。

快慢指针法就是，通过两个指针，块指针一次移动两格，慢指针一次移动一格，如果链表中无环，那么两个指针永远不会相遇，并且块指针走过的步长是慢指针走过步长的两倍。

如果链表中有环路，还可以通过快慢指针法找到环开始的位置，具体参见LeetCode#141和#142。

改变父指针指向的值

在使用单链表情况下，我们很难追溯到父节点，于是父节点指针的改变将非常困难。那么我们可以选择改变当前节点的值，可以等效作改变了父节点的指向。