Java单链表反转问询：不创建新节点、不修改节点数据

Hey there! Great question—this is a classic linked list problem that trips up a lot of folks, especially with those strict constraints. The "runner technique" here refers to using a two-pointer approach to traverse the list and rearrange pointers in place, which fits exactly what you need. Let's break this down step by step.

Core Idea #

Instead of creating new nodes or editing the data inside existing nodes, we'll rearrange the next pointers of each node so that each node points to its previous node instead of the next one. The runner technique (two pointers) helps us keep track of where we are in the list and what we need to point to next, without using extra space beyond a few variables.

Step-by-Step Explanation with Code #

First, let's define a basic singly linked list node structure for context (this is standard setup, not creating new nodes for the reversal itself):

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Now, here's the reversal function using the two-pointer (runner) approach:

def reverse_linked_list(head):
    # Initialize two pointers: prev tracks the previous node, curr tracks current node
    prev = None
    curr = head
    
    while curr is not None:
        # Save the next node first—we're about to overwrite curr.next!
        next_node = curr.next
        # Reverse the current node's pointer to point to prev
        curr.next = prev
        # Move prev up to the current node (it's now the "previous" for the next iteration)
        prev = curr
        # Move curr to the saved next node (continue traversing the list)
        curr = next_node
    
    # When curr is None, prev is the new head of the reversed list
    return prev

Let's Walk Through an Example #

Say we have a list: 1 -> 2 -> 3 -> 4 -> None

1. Start with prev = None, curr = 1
2. Save next_node = 2, set 1.next = None, move prev = 1, curr = 2
3. Save next_node = 3, set 2.next = 1, move prev = 2, curr = 3
4. Save next_node = 4, set 3.next = 2, move prev = 3, curr = 4
5. Save next_node = None, set 4.next = 3, move prev = 4, curr = None
6. Loop ends—return prev (which is 4), giving us 4 -> 3 -> 2 -> 1 -> None

Why This Fits the Runner Technique #

The runner technique is all about using multiple pointers to traverse a list in a way that avoids extra space or redundant passes. Here, curr is our "forward" runner moving through each node, while prev is our trailing runner that lags behind to track where each node should point next. We don't need a counter—just these two pointers to coordinate the reversal seamlessly.

Edge Cases to Consider #

• Empty list: If head is None, the function returns None immediately (correct, since reversing an empty list is still empty).
• Single node: If the list has one node, the loop runs once, sets curr.next = None, and returns prev (the same node—correct, since reversing a single node is itself).

内容的提问来源于stack exchange，提问作者Anthony Rulli