一个关于链表的翻转问题

Question

给定一个链表求链表的翻转
链表的结构为 val 和 next

Answer 1

一、源码

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) 执行删除 now->next 的操作
        return retNode;
    }
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *doRemoveNode = head;                             // (5) doRemoveNode->next 是将要被删除的节点，所以 doRemoveNode 需要被缓存起来，不然都不知道怎么进行删除
        while(doRemoveNode) {                                      // (6) 没有需要删除的节点了
            ListNode *newHead = removeNextAndReturn(doRemoveNode); // (7) 删除 doRemoveNode 的下一个节点并返回被删除的节点
            if(newHead) {                                          // (8) 如果有被删除的节点，则插入头部
                newHead->next = head;                              
                head = newHead;                
            }else {
                break;                                             // (9) 如果没有，则跳出迭代
            }
        }
        return head;
    }
};

二、扩展链接

力扣 https://leetcode-cn.com/problems/UHnkqh/