给定单链表的头节点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; } };