题型一：反转单链表
思路解析
反转一个链表主要是想让第一个节点指向NULL，第二个节点指向第一个，以此类推。那么我们不难想到，想要反转其中一个节点，两个指针肯定是不够的，所以这就要求我们定义三个指针：分别指向当前节点n2，前一个节点n1，后一个节点n3。
这里定义的三个指针主要作用：n1是为了能让当前节点能指向前一个节点地址，而n1就是记录前一个节点的地址，n3是为了在反转当前节点后，能找到后一个节点的地址。
那么定义一个循环后依此思路便可反转链表了。当然循环结束的条件为n3 == NULL，那么再仔细想一下，其实还有最后一个节点没有反转，此节点只需要最后单独反转便可。那么为什么不让循环结束条件为n2 == NULL呢？是因为此时n3 == n2->next而n2又等于NULL，这就导致了错误。
还要一点需要注意的是：在解题前我们还要单独判断一下此链表是否为空。
图解如下：
OJ题实例
LeetCode链接：206. 反转链表
解题代码
struct ListNode* reverseList(struct ListNode* head) { //判断链表为空的情况 if(head==NULL) { return NULL; } else { //反转链表 struct ListNode* n1=NULL; struct ListNode* n2=head; struct ListNode* n3=head->next; while(n3) { n2->next=n1; n1=n2; n2=n3; n3=n3->next; } //最后一个节点的判断 n2->next=n1; return n2; } }
题型二：快慢指针
思路解析
通常快慢指针方法出现在需要找链表中间节点，链表带环等题型中。快慢指针的逻辑思路如下：
先定义两个结构体指针struct ListNode* slow = head, *fast = head;，先将他们指向头节点，在写一个循环，每次循环慢指针向后走一个节点，即slow = slow->next;，快指针向后走两个节点，即fast = fast->next->next;，循环的判断条件为fast != NULL && fast->next != NULL，这样便很好解决了链表为空和只有一个节点的情况。需要注意的是如果节点数为奇slow刚好在中间节点，节点数为偶slow在中间两个节点的后一个。
OJ题实例
LeetCode链接: 876. 链表的中间结点
解题代码
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast=head, *slow=head; while(fast && fast->next) { slow = slow -> next; fast = fast -> next -> next; } return slow; }
两类题型的结合
牛客链接: OR36 链表的回文结构
解题思路：此题可以先找到中间节点，然后把后半部分逆置，然后进行前后两部分一一比对，如果节点的值全部相同，则即为回文。
class PalindromeList { public: bool chkPalindrome(ListNode* A) { if (A == NULL || A->next == NULL) return true; ListNode* slow, *fast, *prev, *cur, *nxt; slow = fast = A; //找到中间节点，即题型二快慢指针 while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } prev = NULL; //后半部分逆置，即题型一链反转 cur = slow; while (cur) { nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } //逐点比对 while (A && prev) { if (A->val != prev->val) return false; A = A->next; prev = prev->next; } return true; } };
