分析
在原来的链表上进行反转空间复杂度 O(1), 稍加思考可知道最少需要三个指针, 那么先处理常规的情况 (结点数大于等于 3 个), 其中该情况又要分别处理头中尾三种情况
最后慢慢处理特殊情况 (结点数 1 个, 结点数 2 个), 然后写出代码
- /*
- struct ListNode {
- int val;
- struct ListNode *next;
- ListNode(int x) :
- val(x), next(NULL) {
- }
- };*/
- class Solution {
- public:
- ListNode* ReverseList(ListNode* pHead) {
- if(pHead == NULL)return NULL;
- ListNode* node1 = pHead;
- ListNode* node2 = pHead->next;
- if(node2==NULL){
- return node1;
- }
- ListNode* node3 = pHead->next->next;
- if(node3==NULL){
- node2->next = node1;
- node1->next = NULL;
- return node2;
- }
- node1->next = NULL;
- node2->next = node1;
- // 进入下一个状态
- node1 = node2;
- node2 = node3;
- node3 = node3->next;
- while(node3 != NULL){
- node2->next = node1;
- // 进入下一个状态
- node1 = node2;
- node2 = node3;
- node3 = node3->next;
- }
- node2->next = node1;
- return node2;
- }
- };
总结
头脑要保持清醒, 指针不要弄混了
来源: http://www.bubuko.com/infodetail-3394740.html