876：链表的中间节点 206：反转链表 143：重排练表
这个题一看就是最简单的快慢指针，但是在具体实现的时候我还是犹豫思考了一下：要不要在链表前面放置哑节点，快指针应该什么时候判断已经到达结尾。但是单纯的想并没有什么结果。对于这种不是算法本身的问题，而只是实现细节的问题，不要多想，没有很大的意义，只要对于每种情况都动手（脑）模拟一遍，看这么样能够让情形变得更加简单即可。
我思考了一下以后写了一下自己的代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* middleNode(ListNode* head) { ListNode *fast = head, *slow = head; while(fast->next != nullptr && fast->next->next !=nullptr) { fast = fast->next->next; slow = slow->next; } if(fast->next == nullptr) return slow; else return slow->next; } };看了一下题解的实现方法，更加的简洁。我的这种虽然能够解决问题，但是没有考虑另一种判断快指针是否到达结尾的方式：fast != nullptr && fast->next != nullptr。以后应该都考虑一下，然后按照最简单的方式实现。
就是将一个链表进行反转。
不知怎么的我把题目看成了反转输出，可能是因为ACM里面很少对原数据进行操作的原因。反转输出我想到的只有递归输出。
有两种方法，迭代法和递归法。迭代法很容易想到，也很容易实现。
在实现迭代法的时候我在想能不能使用C++中的二级指针简化操作（因为一般删除之类的使用二级指针都会方便许多），但是稍微思考一下发现，我们使用二级指针是为了解决无法原地修改指针的问题，但是这个是可以直接修改的（因为每一个节点都要进行修改），而且还必须需要保存前一个节点的信息，因此使用二级指针就完全是鸡肋。
递归法我想的是重新写一个函数，然后进行处理。但是看到题解中一个十分优美的实现方式，虽然效率不一定高（不一定比迭代法低）
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { /* ListNode* pre = nullptr, *cur = head, *next = nullptr; while(cur != nullptr) { next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; */ if(head == nullptr || head->next == nullptr) { return head; } ListNode *tail = reverseList(head->next); head->next->next = head; head->next = nullptr; return tail; } };其中注释部分为迭代法
递归法中比较难理解的就是返回的那个指针是什么，其实这个指针是链表的尾部，也就是新链表的头部。
将链表从头部挑一个，尾部挑一个，然后重复这个过程直到链表为空。
我自己完全没有思路，是学习了题解以后才明白的。
需要分三步完成重排：
找到链表的中点将中点后面的链表反转将前后两个链表合并我手撸了一下，因为才学习了上面两个问题，所以代码写的很流畅，但是为了尽可能少命名变量可能看起来有些迷惑。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(head == nullptr) return; // 求链表的中点 ListNode *fast =head, *slow = head; while(fast->next != nullptr && fast->next->next != nullptr) { fast = fast->next->next; slow = slow->next; } // 将链表的后半部分反转 fast = slow->next; ListNode *pre = nullptr, *next = nullptr; while(fast != nullptr) { next = fast->next; fast->next = pre; pre = fast; fast = next; } fast = pre; //进行合并 slow->next = nullptr; slow = head; while(fast != nullptr) { next = slow->next; slow->next = fast; pre = fast->next; fast->next = next; slow = next; fast = pre; } } };