Trying to solve Odd Even Linked List question.

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

My try:

/**
 * 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) {
        if (head == nullptr || head->next == nullptr) return head;
        int n = 1;
        ListNode* l = nullptr;
        ListNode *u = l;
        ListNode* r = r;
        ListNode* ru = nullptr;
        while(head){
            ListNode* c = new ListNode(head->val);
            if(n%2){
                if(r == nullptr){
                    r = c;
                }
                else{
                    r->next = c;
                    r = r->next;
                }
            }
            else{
                if(l == nullptr){
                    l = c;
                }
                else{
                    l->next = c;
                    l = l->next;
                }
            }
            n  ;
            head=head->next;
        }
        l->next = ru;
        
        return u;
    }
};

But getting the below error:

Line 27: Char 24: runtime error: member access within misaligned address 0x9ddfea08eb382d69 for type 'ListNode', which requires 8 byte alignment (solution.cpp) 0x9ddfea08eb382d69: note: pointer points here SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:36:24

What does the error mean and to solve it.

Link: https://leetcode.com/problems/odd-even-linked-list/

CodePudding user response：

The problem is (once we fix the typo):

ListNode *l = nullptr;
ListNode *u = l;
...
return u;

u is always nullptr. One quick hack would be:

ListNode *l = nullptr;
ListNode **u = &l;
ListNode *r = nullptr;
ListNode **ru = &r;
...
l->next = *ru;
return *u;

Or you could try:

if(r == nullptr){
    r = c;
    ru = r;  // Add this
}
...
if(l == nullptr){
    l = c;
    u = l;  // Add this
}

CodePudding user response：

Please check the code with comments marked as // CHANGE HERE

Tested here: https://godbolt.org/z/c3e5M739d

#include <iostream>
 
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) {
        if (head == nullptr || head->next == nullptr) return head;
        int n = 1;
        // CHANGE HERE: set all to nullptr
        ListNode* l = nullptr;
        ListNode* u = nullptr;
        ListNode* r = nullptr;
        ListNode* ru = nullptr;
        while(head){
            // std::cout << head->val << " ";
            ListNode* c = new ListNode(head->val);
            if(n%2){
                // CHANGE HERE: replace r with ru
                if(ru == nullptr){
                    r = c;
                    // CHANGE HERE: set ru
                    ru = r;
                }
                else{
                    r->next = c;
                    r = r->next;
                }
            }
            else{
                // CHANGE HERE: replace l with u
                if(u == nullptr){
                    l = c;
                    // CHANGE HERE: set u
                    u = l;
                }
                else{
                    l->next = c;
                    l = l->next;
                }
            }
            n  ;
            head=head->next;
        }
        l->next = ru;
        
        return u;
    }
};

int main()
{
    ListNode* node = new ListNode(1);
    node->next = new ListNode(2);
    node->next->next = new ListNode(3);
    node->next->next->next = new ListNode(4);
    node->next->next->next->next = new ListNode(5);
    node->next->next->next->next->next = new ListNode(6);

    Solution s;
    ListNode* l = s.oddEvenList(node);

    ListNode* q = l;
    while (q)
    {
        std::cout << q->val << " ";
        q = q->next;
    }
}