leetcode 206 反转链表 / reverse linked list

题目描述：

这道题应该是一道比较经典的面试题了，思路有迭代和递归两种，个人觉得两种都理解还是需要一定时间思考的，这题tag应该为普通。

递归：时间复杂度o(n),空间复杂度o(n)(此写法每层空间都要传头结点）

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head -> next == NULL){
            return head;
        }
        ListNode* newHead = reverseList(head -> next);//每层都要把新的头指针（最后一个元素）传上去
        head -> next -> next = head;
        head -> next = NULL;//要修改成NULL,不然就成了双向链表了
        return newHead;
    }
};

迭代：时间复杂度o(n),空间复杂度o(1)

关于迭代这里自己遇到个大坑。。。自己首先是看了看别人的算法，觉得懂了，然后自己写。结果写出来发现居然超时？？？

然后仔细看了看别人的写法和自己的写法差异在哪里。。

别人的：

class Solution {
	public:
		ListNode* reverseList(ListNode* head) {
			if (head == NULL) return NULL;
			ListNode *pre = head;
			ListNode *cur = head->next;
			while (cur != NULL)
			{
				pre->next = cur->next;
				cur->next = head;
				head = cur;
				cur = pre->next;
			}

			return head;
		}
	};

自己的：

/**
 * 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) {
        if(head == NULL) return NULL;
        if(head -> next == NULL) return head;
        ListNode* p = head;
        ListNode* q = head -> next;
        ListNode* temp;
        while(q != NULL){
            temp = q -> next;// !!!!!!!!!!!!!!!!!!问题就出在这里
            q -> next = p;
            p = q;
            q = temp;
        }
        return p;
    }
};

差异就在我注释感叹号的那一句，由于我用的一个temp变量来记录每次需要更新的点，这样做法的错误之处就是没有改掉1号节点的next域，1号节点的next域还是指向2号节点，这样就会导致最后的跑出来的结果一直在1号节点和2号节点之间循环跑。。。不超时才怪了。