在解决链表问题时创建一个额外的节点是一个好习惯吗？

Is creating an extra node when solving linked list question a good habit?

最近，我一直在研究 LeetCode 上的链表问题，我注意到在处理链表（如排序链表）时，人们有时会创建一个 虚拟节点 和 return dummy->next。这是一个非常方便的行为，但是这样做会不会有任何不好的结果（比如说，如果我最后删除它以避免内存泄漏）？或者，是否有任何情况使此行为不合适？

下面的代码是一个例子，ohead是我的dummy节点：

/**
 * 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* oddEvenList(ListNode* head) {
        ListNode *ohead = new ListNode, *ehead = new ListNode;
        ListNode *optr  = ohead, *eptr = ehead;
        bool isOdd = true;
        for(auto ptr = head; ptr; ptr = ptr->next){
            if(isOdd){
                optr->next = ptr;
                optr = optr->next;
            }
            else{
                eptr->next = ptr;
                eptr = eptr->next;
            }
            isOdd = !isOdd; //update isOdd
        }
        optr->next = ehead->next;
        eptr->next = nullptr;
        return (ohead->next);
    }
};

没有，新建节点没有问题。因为解决 LeetCode 问题最重要的是算法的效率（时间和内存复杂度）。添加一个新节点是恒定的时间和内存，不会改变解决方案的复杂性。

这是一个 O(N) 时间和 O(1) space 解决方案，可以通过 LeetCode 的“在线法官”来解决您要解决的问题：

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode* odd = head;
        ListNode* even_head = head->next;
        ListNode* even = even_head;

        while (even && even->next) {
            odd->next = odd->next->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }

        odd->next = even_head;

        return head;
    }
};

参考资料