链表两两交换节点两种实现的时间与内存效率差异疑问

你的两个实现 #

交换节点值的实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* p = head;
        int temp = 0;
        while(p!= NULL && p->next!=NULL)
        {
            temp = p->val;
            p->val = p->next->val;
            p->next->val = temp;
            p = p->next->next;
        }
        return head;
    }
};

修改连接关系的实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* p = head;
        ListNode* q = head;
        ListNode* r = head;
        int flag = 0;
        while(p!= NULL && p->next!=NULL)
        {
            if(flag == 0)
            {
                flag = 1;
                q = p->next;
                p->next = q->next;
                q->next = p;
                head = q;
                p = q->next->next;
                r = q->next;
                continue;
            }
            q = p->next;
            p->next = q->next;
            q->next = p;
            r->next = q;
            p = q->next->next;
            r = q->next;
        }
        return head;
    }
};

核心原因分析 #

1. 操作本质的差异

• 交换节点值的实现：每次循环需要完成三次int类型的内存读写（将p的val存入temp，把p->next的val赋值给p的val，再把temp赋值给p->next的val），涉及两个不同节点的val字段访问。
• 修改连接的实现：每次循环完成三次指针类型的赋值（调整p、q、r的next指针指向），操作的是链表节点的next指针。

在现代CPU中，指针赋值和int赋值的指令周期相近，但指针操作往往更容易被编译器优化——指针是固定大小的地址类型，编译器可以生成更紧凑的指令；而val字段的读写可能因为内存地址分布，导致缓存命中率略低（连续访问不同节点的val，逻辑上不如指针操作贴合链表遍历的缓存友好模式）。

2. 栈内存占用的误解

你觉得第一个实现变量更少所以内存占用更低，但实际上：

• 栈上的指针和int变量占用内存极小（64位系统下每个指针仅8字节，int是4字节），三个指针加一个flag的总栈内存不到32字节，和第一个实现的12字节差异可以完全忽略。
• 你看到的内存占用差异，大概率是测试平台对运行时缓存开销的统计，而非栈内存的差异。交换值的实现需要频繁读写不同节点的val，可能导致更多缓存失效，从而被统计为更高的内存占用。

3. 测试平台的波动

OJ平台的运行时间和内存统计存在一定波动，单次测试结果不一定完全准确。多次测试后，两者的差异可能缩小甚至反转。但从算法本质来看，修改连接的实现更贴合题目要求（不修改节点值），且多数场景下性能表现更稳定。

补充：题目合规性 #

需要注意，题目明确要求「不能修改节点中的值，只能修改节点本身的连接关系」，第一个实现其实不符合题目要求，属于钻空子的解法，仅能通过测试但不满足题意约束。

内容的提问来源于stack exchange，提问作者Preeti Sharma