Splitting linked list return with segmentation fault-CodePudding

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();

CodePudding user response：

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.

CodePudding user response：

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