反转链表 反转链表图解

给定单链表的头节点head ，要求反转链表，并返回反转后的链表头

思路分析:头插法,每次拿出第2个结点插到头部,拿出第3个节点,拿出第 4 个节点插到头部，… 拿出最后一个节点插到头部.

删除第i个结点,将它放在头部,反复迭代

class Solution {
    ListNode *removeNextAndReturn(ListNode* now) {                 // (1) 删除now的next结点并返回
        if(now == nullptr || now->next == nullptr) {
            return nullptr;                                        // (2) 本身为空或者下一个结点为空,返回空
        }
        ListNode *retNode = now->next;                             // (3) 将需要删除的结点缓存起来
        now->next = now->next->next;                               // (4) 执行删除操作
        return retNode;
    }
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *doRemoveNode = head;                             // (5) 缓冲
        while(doRemoveNode) {                                      // (6) 没有需要删除的结点就结束迭代
            ListNode *newHead = removeNextAndReturn(doRemoveNode); // (7) 删除下一个结点,并返回
            if(newHead) {                                          // (8) 如果有被删除的结点,则插入头部
                newHead->next = head;                              
                head = newHead;                
            }else {
                break;                                             // (9) 没有跳出
            }
        }
        return head;
    }
};