Splitting linked list return with segmentation fault

Question

i am trying to build a split function for a linkedlist, so i need to split my linkedlist into a half and i need to update the size of linkedlist as well, when i execute my code it returned with segmentation fault i am not sure what is wrong with my code can you help me thank you :), i am sorry for bad code

LinkedList<T> LinkedList<T>::split() {
    Node* head_ptr = this -> head_;
    LinkedList<int>* other = new LinkedList<int>();

    
    if(this -> size_ % 2 != 0){
        this -> size_ += 1;
    } 

    int a = this -> size_ / 2;
    int i = 1;
    
    while(i < a){
        head_ptr = head_ptr -> next;
    }

    other -> head_ = head_ptr -> next;
    head_ptr -> next = nullptr;
    Node * new_other = other -> head_;
    
    while(new_other != nullptr){
        other -> size_++;
        new_other = new_other -> next;
    }

    this -> size_ = this -> size_ / 2;
    return *other;

}

For my node structure:

class Node
    {
    public:
        T data{};
        Node* next = nullptr;

    };

For my LinkedList class:

template <typename T>
class LinkedList
{
private Node* head_ = nullptr;
private int size_ = 0;
LinkedList(const LinkedList<T>& other);
LinkedList(std::initializer_list<T> input);
void push(const T& data);
void pop();
LinkedList<T> LinkedList<t>::split();

Why the list is dynamically allocated LinkedList<int>* other = new LinkedList<int>();?! Show the definition of the list. — Vlad from Moscow
– Vlad from Moscow, Commented Apr 22, 2022 at 7:37
You might also want to take a look at Why should C++ programmers minimize use of 'new'?. — Erel
– Erel, Commented Apr 22, 2022 at 7:57
Should the new linked list share nodes with the original one or should the nodes be copied? — Sebastian
– Sebastian, Commented Apr 22, 2022 at 8:07

WhozCraig · Accepted Answer · 2022-04-22 08:59:15Z

2

Splitting a linked list given only the head pointer involves walking the list with a slow and fast pointer, and it seems somewhat evident you already know this. The difficult part is knowing where to terminate and how to then handle the two resulting lists.

First, make a private ctor that only you will be calling (from something like your split()). The purpose of this is to feed a new LinkedList instance a predetermined list head and size. It will come in handy later. It may look like this (assuming it is in your class-def, otherwise adjust accordingly):

// purposely private
LinkedList(Node *head, size_t siz)
    : head_(head)
    , size_(siz)
{
}

Armed with that, you can make a trivial splitter by using a slow-pointer that happens to also be a pointer-to-pointer (which will become very handy for setting the left-side list terminator), and a fast pointer to double-hop the list as long as possible.

LinkedList split()
{
    size_t lsize = 0;
    Node **pp = &head_;
    Node *fast = head_;
    while (fast && fast->next)
    {
        ++lsize;
        pp = &(*pp)->next;
        fast = fast->next->next;
    }

    Node *p = *pp; // remember head of right list
    *pp = nullptr; // terminate left list

    // adjust sizes
    size_t rsize = size_ - lsize;
    size_ = lsize;

    return LinkedList(p, rsize); // remember that funky ctor??
}

That's all there is to it. Note that due to the even/odd possible node count, this will always bias the right side getting the extra node if there is one. If the count is even this will split the list perfectly, retaining the left side in the current list and returning the right side as the result value. Also note that if you invoke this with a single-node list the current list will be emptied and the return result will harbor that single node.

edited Apr 22, 2022 at 8:59

answered Apr 22, 2022 at 8:48

WhozCraig

66.5k11 gold badges82 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

David C. Rankin Over a year ago

They are going to need your victim lesson in a later question. The Crystal-Ball never fails... :)

WhozCraig Over a year ago

@DavidC.Rankin LOLz. I haven't written a destroyer-of-victims in quite some time. Probably coming due.

PCDSandwichMan · Accepted Answer · 2022-04-22 08:03:45Z

1

I had a bit of trouble understanding how you wanted to handle the split but could you try something like this?

LinkedList<T> LinkedList<T>::split() {
    LinkedList<T> second_list;
    Node* current = head_;
    Node* second_current = second_list.head_;

    while (current->next != nullptr) {
        if (current->next->next != nullptr) {
            current = current->next->next;
            second_current = second_current->next;
        }
        else {
            current = current->next;
            second_current = second_current->next;
        }
    }
    
    current->next = nullptr;
    second_current->next = nullptr;
    return second_list;
}

edited Apr 22, 2022 at 8:03

answered Apr 22, 2022 at 7:36

PCDSandwichMan

2,1581 gold badge15 silver badges27 bronze badges

8 Comments

CloverZZ Over a year ago

hi thank you for your answer, i need to split the linkedlist into a half and i need to update the size of the linkedlist as well, i will update my code to show my Node Structure

PCDSandwichMan Over a year ago

you might want to share the LinkedList model as well but I will update the example

CloverZZ Over a year ago

Done can you have a look

PCDSandwichMan Over a year ago

Do you want the first half or the second half returned?

CloverZZ Over a year ago

the second half

|

Collectives™ on Stack Overflow

Splitting linked list return with segmentation fault

2 Answers 2

2 Comments

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related