描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例1

输入：

{1,2,3}

返回值：

{3,2,1}

示例2

输入：

{}

返回值：

{}

说明：

空链表则输出空  

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.给定一个单链表的头节点pHead

（该头节点是有值的，比如上图，它的val是1），

2.长度为n，

3.反转该链表后，

4.返回新链表的表头

5.数据范围：n大于等于0小于等于1000

6.要求：空间复杂度O（1），时间复杂度O（n）。

7.如当输入链表{1，2，3}时，经翻转后，原链表变为{3，2，1}，所以对应的输出为{3，2，1}。

二、解题思路

1.因为需要反转链表，所以当前节点下一个节点的next要指向当前节点

比如1->2->3->NULL

如果我们反转链表，我们希望变成3->2->1->NULL

所以如果我们的头节点head的值是1，我们希望建立一个临时节点temp = head；

这个时候头节点和temp都是节点1

我们希望改变1的状态，让1的next变成NULL，并且让节点2的next变成1

我们为了不丢失下一个节点，我们需要建立一个临时节点tempnext = temp->next;

这样的话tempnext节点就是节点2，

我们先将节点1的状态改变，temp->next = NULL;

这样我们得到了temp：1->NULL和tempnext：2->3->NULL;

因为tempnext->next还有值，所以我们还需要记录tempnext->next的值为tempnextnext = tempnext->next;

然后我们使用tempnext->next = temp

这样我们得到了tempnext：2->1->NULL 和tempnextnext：3->NULL;

我们可以按照上面的逻辑，将temp = tempnext；

tempnext = tempnextnext；

然后当tempnext->next 不为NULL的时候我们重复

while(tempnext->next != NULL) {

tempnextnext = tempnext->next;

tempnext->next = temp;

temp = tempnext;

tempnext = tempnextnext;

}

最后如果出了循环证明是tempnext->next是NULL

我们将

tempnext->next指向temp就行了

然后返回tempnext

如果链表为空或者只有一个元素时候我们直接返回链表本身。

如果链表只有两个元素我们将第二个元素指向第一个元素，然后第一个元素指向NULL。

三个以上的情况用刚才的方法就可以了

三、具体步骤

使用的语言是C

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    if(head == NULL) {
        return head;
    }
    if(head->next == NULL) {
        return head;
    }
    struct ListNode* temp = head;
    struct ListNode* tempnext = temp->next;
    if(head->next->next == NULL) {
        tempnext->next = temp;
        temp->next = NULL;
        head = tempnext;
        return head;
    }
    struct ListNode* tempnextnext = tempnext->next;
    temp->next = NULL;
    tempnext->next = temp;
    temp = tempnext;
    tempnext = tempnextnext;
    while(tempnext->next != NULL) {
        tempnextnext = tempnext->next;
        tempnext->next = temp;
        temp = tempnext;
        tempnext = tempnextnext;
    }
    tempnext->next = temp;
    head = tempnext;
    return head;

}

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    if(head == NULL) return head;
    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    while(cur != NULL) {
        struct ListNode *next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
} 

看了官方题解之后简化了

如果输入为空直接返回原来的head

否则的话我们只要记住我们主要任务是将cur->next = pre;

然后不停更新cur pre的值，为此我们需要一个临时变量next存储我们下一个节点（因为如果不存储的话我们cur->next一旦改变我们会丢失下一个节点）

所以实际上我们需要不停更新pre cur next,然后cur指针不停指向pre（反转）（之前是pre->next = cur）

还有一点就是，我们一开始可以将pre这个节点设置为NULL，将当前节点cur设置为head，这样刚好反转过来之后我们最后一个节点指向NULL

1）pre = NULL;

2）cur = head;

NULL       1->2->3->NULL

pre         cur

3）next = cur->next;

NULL         1->        2->3->NULL

pre         cur          next

4）cur->next = pre;

NULL  <-1               2->3->NULL

pre         cur          next

然后我们就不需要pre这个节点做什么了因为已经完成反转了

我们就可以更新pre为cur

5）pre = cur;

NULL<-1            2->3->NULL

           cur          next

           pre

更新cur为next

6）cur = next;

NULL<-1            2->3->NULL

            pre      next

                        cur

更新next为next

7）next = next->next;

NULL<-1            2->        3->NULL

            pre      cur         next

8）然后重复4）-7）

cur->next = pre;

NULL<-1     <-2    3->NULL

             pre cur    next

pre = cur;

NULL<-1     <-2    3->NULL

                    cur    next

                   pre

cur = next;

NULL<-1     <-2    3->NULL

                     pre  next

                             cur

next = next->next;

NULL<-1     <-2    3->NULL

                     pre    cur    next

cur->next = pre;

NULL<-1     <-2    <-3    NULL

                     pre    cur    next

pre = cur;

NULL<-1     <-2    <-3    NULL

                             cur    next

                              pre

cur = next;

NULL<-1     <-2    <-3    NULL

                             pre    next

                                      cur

（因为我们循环里写的是   

while(cur != NULL) {
        struct ListNode *next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }

所以必须执行到cur=next;）

所以这个时候我们返回的是pre而不是cur