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

user_10464276 0
Viewed 205

Lately, I've been working on linked list questions on LeetCode, and I noticed that when dealing with linked lists (like sorting linked lists), people sometimes create a dummy node and return dummy->next. It is a pretty convenient act, but are there any bad outcomes from doing this (say, if I will delete it in the end to avoid a memory leak)? Or, are there any situations that make this act inappropriate?

The code below is an example, ohead is my dummy node:

/**
 * 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);
    }
};
singly-linked-list linked-list algorithm c++
1 Answers

No, creating a new node has no problem. Because all it matters in solving LeetCode questions is the efficiency of your algorithm (time and memory complexity). Adding one new node is constant time and memory and would not change the complexity of your solution.

Here is an O(N) time and O(1) space solution that would pass LeetCode's "Online Judge" for the problem you're trying to solve:

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;
    }
};

References

user_65533280
Related