You are given the head pointer of a singly linked list. Write a function that reverses the entire list in-place and returns a pointer to the new head. You may only use the head pointer that is passed to you—no dummy nodes, no extra lists, and no recursion stacks that grow with n. All node objects already exist; you must relink them, not create or destroy any nodes. The algorithm must run in O(n) time and O(1) additional space.

视频信息

答案文本 复制

视频字幕 复制

We need to reverse a singly linked list in-place. Given a head pointer to the original list, we must relink the nodes so that the last node becomes the new head, and all arrows point in the opposite direction. The challenge is to do this efficiently using only constant extra space. The key insight is to use three pointers to track our position and safely reverse the links. We start with prev pointing to NULL, current pointing to the head, and next_node initially NULL. This setup allows us to reverse one link at a time while keeping track of where we are in the list. Let's trace through the algorithm step by step. Initially, prev points to NULL and current points to the first node. In each iteration, we store the next node, reverse the current link to point backwards, then advance both pointers. Watch how the reversed portion grows with each step. Here's the complete implementation in C++. The algorithm is elegant in its simplicity - we use only three pointers and process each node exactly once. The time complexity is O(n) since we visit every node, and space complexity is O(1) since we only use a constant amount of extra memory regardless of input size.