题目
题目一：.反转一个单链表
思路1
可以用三个节点依次翻转，中间节点指向反转，交换三个节点指针，更新，直到原链表遍历完。但这里要求链表至少有2个节点（第三个节点可以是NULL）。所以，我们可以在开始进行判断，当链表为空或者链表少于2个节点。我们直接返回头指针就行。
空链表
直接返回
一个节点
反转过来就是自己本身。所以，可以直接返回
思路2
逐个头插到一个新链表，不断更新newhead。cur与next接替节点。这种思路方便的就是不用分类。
代码1
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL || head->next == NULL)return head;struct ListNode* n1, *n2, *n3;n1 = head;n2 = n1->next;n3 = n2->next;n1->next = NULL;//中间节点不为空，继续修改指向while(n2){//中间节点指向反转n2->next = n1;//更新三个连续的节点n1 = n2;n2 = n3;if(n3)n3 = n3->next;}//返回新的头return n1;
}代码2
// 取节点头插的思想完成逆置
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;struct ListNode* cur = head;while(cur){struct ListNode* next = cur->next;//头插新节点，更新头cur->next = newhead;newhead = cur;cur = next;}return newhead;
}题目二：链表的中间节点
思路
使用快慢指针，cur每次走两步，prev每次走一步。prev的路程是cur的一半。当cur走完时，prev刚好就是中间那个节点
代码
/*
解题思路：
通过快慢指针找到中间节点，快指针每次走两步，慢指针每次走一步，当快指针走到结尾的时候，慢指针正好走到中间位置
*/
typedef struct ListNode Node;
struct ListNode* middleNode(struct ListNode* head){Node* slow = head;Node* fast = head;while(fast!=NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;}return slow;
}题目三：返回倒数的第k个节点
思路
快慢指针，控制区间段。先让fast走k步，再让fast与slow一起走。当fast走完时，slow就是指向倒数第k个节点的指针
代码
/*
解题思路：
快慢指针法 fast, slow, 首先让fast先走k步，然后fast,slow同时走，fast走到末尾时，slow走到倒数第k个节点。
*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {struct ListNode* slow = pListHead;struct ListNode* fast = slow;while(k--){if(fast)fast = fast->next;elsereturn NULL;}while(fast){slow = slow->next;fast = fast->next;}return slow;}
};题目四：合并两个有序链表
思路
和有序数组的合并思路类似。都是依次比较，取更小的数据插入。不过这里是链表，不方便尾插。所以，我们创建一个带哨兵位的链表，再创建一个尾指针（方便尾插）。依次把更小的数据尾插到新链表上，最后再把新链表的next返回。因为这里给你的是你一个不带哨兵位的链表。所以，你返回的时候也不要带哨兵位的链表。
这里使用哨兵位的链表会很方便。如果你的新链表不带哨兵位，那你还要考虑给新的newhead赋值。
代码
/*
解题思路：
此题可以先创建一个空链表，然后依次从两个有序链表中选取最小的进行尾插操作进行合并。
*/
typedef struct ListNode Node;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){if(l1 == NULL)return l2;else if(l2 == NULL)return l1;Node* head = NULL, *tail = NULL;//创建空链表head = tail = (Node*)malloc(sizeof(Node));tail->next = NULL;while(l1 && l2){// 取小的进行尾插if(l1->val < l2->val){tail->next = l1;tail = tail->next;l1 = l1->next;}else{tail->next = l2;tail = tail->next;l2 = l2->next;}}//剩余元素直接拼接if(l1)tail->next = l1;elsetail->next = l2;Node* list = head->next;free(head);return list;
}总结
这几道题都是关于链表的，大多题目的思路都和双指针有关。所以，可见双指针在解决链表的一些题目上有很大作用。这可以当成一个题解的基本思路。从双指针出发，根据题目特点进行变型，解决题目。解决这类题目，画图也是一个很好的方法。当你在写代码前，先画图把思路弄清楚，会大大提高你代码的正确率。即使代码错了，也可以通过图来走读你的代码。如果都不行，我们再调试代码。这能提高你解决题目的效率，不然你很有可能是调试了两三个小时都发现不了问题。
