题解 | #反转链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
/*
思考逻辑总结：
	1、链表要反向---》哪些链表不需要反向---》1）空链表不需要；2）只有一个数值的链表也不需要；都只需要返回head
	2、链表要反向---》如何反向--》方案一：创建一个新链表，在遍历链表时头插入数据到新链表中；方案二使用3个指针挪动；
	3、这里采用方案二：要考虑的边界问题：当有指针指向最后一个节点，下一个即将为空时。
	4、注意：链表尾部为空，反向后原来的头部链表为空。
*/
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct ListNode *now_last=head;
    struct ListNode *now=head->next;
    //链表不为空
    if(now_last!=NULL&&now!=NULL)
    {
        struct ListNode *now_next=now->next;
        while(now_next->next!=NULL)
        {
            //反转链表
            now->next=now_last;
            //指针都向下移动
            now_last=now;
            now=now_next;
            now_next=now_next->next;
        }
        now->next=now_last;
        now_last=now;
        now=now_next;
        now->next=now_last;
        //链表尾部处理
        head->next=NULL;
        head=now;
    }
    return head;
}

/*在成功的基础上优化：
struct ListNode* ReverseList(struct ListNode* head ) {
    // write code here
    struct ListNode *now_last=head;
    struct ListNode *now=head->next;
    //链表不为空
    if(now_last!=NULL&&now!=NULL)
    {
        struct ListNode *now_next=now->next;
        while(now_next->next!=NULL)
        {
            //反转链表
            now->next=now_last;
			if(now->next!=NULL)
			{
			  //指针都向下移动
			  now_last=now;
			  now=now_next;
			  if（now_next->next!=NULL） {now_next=now_next->next;}
			}
        }
        //链表尾部处理
        head->next=NULL;
        head=now;
    }
    return head;
}

/