How to reverse a chain of linked memory in a linked list?

Question

Right now, I'm trying to write a reverse method for a Doubly Linked List. It's not just one of the methods where you reverse from start to finish, but specifically a part of the list starting from one point and ending at a point after the start. The method takes in ListNode pointer references called startPoint and endPoint, and they should point at the new start and end of the chain in the linked memory. The next member of the ListNode before the start of the sequence (so startPoint->prev) should point at the new start, and the prev member of the ListNode after the end of the sequence (so endPoint->next) should point to the new end.

A key aspect I should point out is that we may NOT allocate any new ListNodes.

In my List.h file, I have a private class ListNode. I provided that along with the rest of my List class:

template <class T>
class List {
  private:
    class ListNode {
      public:
        ListNode();
        ListNode(const T & ndata);
        ListNode* next;
        ListNode* prev;
        const T data;
    };

  public:
    List();
    List(const List<T>& other);
    List<T>& operator=(const List<T>& rhs);
    int size() const;
    void print(ostream& os = std::cout) const;
    bool empty() const;
    ~List();
    void insertFront(const T& ndata);
    void insertBack(const T& ndata);
    void reverse();
    void tripleRotate();
    List<T> split(int splitPoint);

  private:
    ListNode* head_;
    ListNode* tail_;
    int length_;
    void _copy(const List<T>& other);
    void _destroy();

    /**
     * Helper function to reverse a sequence of linked memory inside a
     * List, starting at startPoint and ending at endPoint. You are
     * responsible for updating startPoint and endPoint to point to the
     * new starting and ending points of the rearranged sequence of
     * linked memory in question.
     *
     * @param startPoint A pointer reference to the first node in the
     *  sequence to be reversed.
     * @param endPoint A pointer reference to the last node in the
     *  sequence to be reversed.
     */
    void reverse(ListNode*& startPoint, ListNode*& endPoint);
};

In my List.hpp file, I have the reverse method itself. I am lost on how exactly to write it. Here's what I have so far (it obviously doesn't work):

template <typename T>
void List<T>::reverse(ListNode *& startPoint, ListNode *& endPoint) {
  if (startPoint == endPoint) {
    return;
  }
  //startPoint should point at the new start, endPoint should point at the new end.
  ListNode* current = startPoint;
  ListNode* before_start_point = startPoint->prev;
  ListNode* after_end_point = endPoint->next;
  while (current != after_end_point) {
    ListNode* temp = current->next;
    current->next = current->prev;
    current->prev = temp;
    if (temp == endPoint) {
      endPoint = startPoint;
      startPoint = current;
    }
    current = temp;
  }
}

The rest of the List.hpp file:

template <class T>
List<T>::List() { 
    head_ = NULL;
    tail_ = NULL;
    length_ = 0;
}

template <typename T>
void List<T>::_destroy() {
  ListNode* current = head_;
  while (current != NULL) {
    ListNode* temp = current->next;
    delete current;
    current = temp;
  }
}

template <typename T>
void List<T>::insertFront(T const & ndata) {
  ListNode* newNode = new ListNode(ndata);
  //Case where there the list is empty
  if (head_ == NULL) {
    head_ = newNode;
    tail_ = newNode;
    newNode->next = NULL;
    newNode->prev = NULL;
  }
  else {
    newNode->next = head_;
    newNode->prev = NULL;
    head_->prev = newNode;
    head_ = newNode;
  }
  length_++;
}

template <typename T>
void List<T>::insertBack(const T & ndata) {
  ListNode* newNode = new ListNode(ndata);
  if (tail_ == NULL) {
    head_ = newNode;
    tail_ = newNode;
    newNode->next = NULL;
    newNode->prev = NULL;
  }
  else {
    newNode->prev = tail_;
    newNode->next = NULL;
    tail_->next = newNode;
    tail_ = newNode;
  }
  length_++;
}

template <typename T>
typename List<T>::ListNode* List<T>::split(ListNode* start, int splitPoint) {
  //There will be splitPoint number of nodes remaining in the current list
  ListNode* curr = start;
  if (splitPoint == 0) {
    return curr;
  }

  //Takes you to the start of the new list
  for (int i = 0; i < splitPoint && curr != NULL; i++) {
    curr = curr->next;
  }

  if (curr != NULL) {
      curr->prev->next = NULL;
      curr->prev = NULL;
  }

  //Return the head of the new sublist
  return curr;
}

template <typename T>
void List<T>::tripleRotate() {
  if (length_ < 3) {
    return;
  }
  else {
    int third_element_counter = 1;
    bool first_rotation = true;
    int divisible_by_three = length_ % 3;
    ListNode* current = head_;
    while (current != NULL) {
      if (third_element_counter != 3) {
        third_element_counter++;
      }
      else {
        ListNode* first = current->prev->prev;
        ListNode* temp_first_prev = first->prev;
        ListNode* second = current->prev;
        ListNode* temp_current = current;
        ListNode* temp_current_next = current->next; 
        second->prev = temp_first_prev;
        if (temp_first_prev != NULL) {
          temp_first_prev->next = second;
        }
        if (temp_current_next != NULL) {
          temp_current_next->prev = first;
        }
        current->next = first;
        first->next = temp_current_next;
        first->prev = temp_current;
        if (first_rotation) {
          head_ = second;
          first_rotation = false;
        }
        if (divisible_by_three == 0) {
          tail_ = first;
        }
        current = first;
        third_element_counter = 1;
      }
      current = current->next;
    }
  }
}

template <typename T>
void List<T>::reverse() {
  reverse(head_, tail_);
}

Any sort of help is appreciated.

Answer 1

Given your code, I manually created a list of ten integers:

    List<int> my_list;
    for(int i = 0; i < 10; i++) {
        my_list.insertBack(i);
    }

Then, I printed the list:

std::cout << "Before reverse:" << std::endl;
    my_list.print();

The output was:

Before reverse:
Node: 0
Node: 1
Node: 2
Node: 3
Node: 4
Node: 5
Node: 6
Node: 7
Node: 8
Node: 9

Then, I ran a slightly modified version of your reverse function:

template <typename T>
void List<T>::reverse(ListNode *& startPoint, ListNode *& endPoint) {
  if (startPoint == endPoint) {
    return;
  }

  //startPoint should point at the new start, endPoint should point at the new end.
  ListNode* current = startPoint;
  ListNode* before_start_point = startPoint->prev;
  ListNode* after_end_point = endPoint->next;
  while (current != after_end_point) {
    std::cout << "Working with current node " << current->data << std::endl;
    ListNode* temp = current->next;
    std::cout << "Temp is " << (temp ? temp->data : 0) << std::endl;
    current->next = current->prev;
    std::cout << current->data << "'s new next is now " << (current->next ? current->next->data : 0) << std::endl;
    current->prev = temp;
    std::cout << current->data << "'s new prev is now " << (current->prev ? current->prev->data : 0) << std::endl;

    if (temp == endPoint) {
      endPoint = startPoint;
      startPoint = temp;
    }
    current = temp;
  }
}

And printed again:

    std::cout << "After reverse:" << std::endl;
    my_list.print();

The output was:

After reverse:
Node: 9
Node: 8
Node: 7
Node: 6
Node: 5
Node: 4
Node: 3
Node: 2
Node: 1
Node: 0

So it seems the only problem was in the if block at the end of the while loop, where you were assigning startPoint = current when instead it should be either startPoint = endPoint or startPoint = temp (because when the if is true, temp is equal to endPoint).

This is the complete code (also available in https://godbolt.org/z/nad7vT):

#include <iostream>

template <class T>
class List {
  private:
    class ListNode {
      public:
        ListNode();
        ListNode(const T & ndata) : data{ndata} {};
        ListNode* next;
        ListNode* prev;
        const T data;
    };

  public:
    List();
    List(const List<T>& other);
    List<T>& operator=(const List<T>& rhs);
    int size() const;
    void print(std::ostream& os = std::cout) const;
    bool empty() const;
    ~List() {};
    void insertFront(const T& ndata);
    void insertBack(const T& ndata);
    void reverse();
    void reverseNth(int n);
    void tripleRotate();
    List<T> split(int splitPoint);

  private:
    ListNode* head_;
    ListNode* tail_;
    int length_;
    void _copy(const List<T>& other);
    void _destroy();

    /**
     * Helper function to reverse a sequence of linked memory inside a
     * List, starting at startPoint and ending at endPoint. You are
     * responsible for updating startPoint and endPoint to point to the
     * new starting and ending points of the rearranged sequence of
     * linked memory in question.
     *
     * @param startPoint A pointer reference to the first node in the
     *  sequence to be reversed.
     * @param endPoint A pointer reference to the last node in the
     *  sequence to be reversed.
     */
    void reverse(ListNode*& startPoint, ListNode*& endPoint);
};

template <typename T>
void List<T>::reverse(ListNode *& startPoint, ListNode *& endPoint) {
  if (startPoint == endPoint) {
    return;
  }

  //startPoint should point at the new start, endPoint should point at the new end.
  ListNode* current = startPoint;
  ListNode* before_start_point = startPoint->prev;
  ListNode* after_end_point = endPoint->next;
  while (current != after_end_point) {
    std::cout << "Working with current node " << current->data << std::endl;
    ListNode* temp = current->next;
    std::cout << "Temp is " << (temp ? temp->data : 0) << std::endl;
    current->next = current->prev;
    std::cout << current->data << "'s new next is now " << (current->next ? current->next->data : 0) << std::endl;
    current->prev = temp;
    std::cout << current->data << "'s new prev is now " << (current->prev ? current->prev->data : 0) << std::endl;

    if (temp == endPoint) {
      endPoint = startPoint;
      startPoint = temp;
    }
    current = temp;
  }
}

template <class T>
List<T>::List() { 
    head_ = NULL;
    tail_ = NULL;
    length_ = 0;
}

template <typename T>
void List<T>::_destroy() {
  ListNode* current = head_;
  while (current != NULL) {
    ListNode* temp = current->next;
    delete current;
    current = temp;
  }
}

template <typename T>
void List<T>::insertFront(T const & ndata) {
  ListNode* newNode = new ListNode(ndata);
  //Case where there the list is empty
  if (head_ == NULL) {
    head_ = newNode;
    tail_ = newNode;
    newNode->next = NULL;
    newNode->prev = NULL;
  }
  else {
    newNode->next = head_;
    newNode->prev = NULL;
    head_->prev = newNode;
    head_ = newNode;
  }
  length_++;
}

template <typename T>
void List<T>::insertBack(const T & ndata) {
  ListNode* newNode = new ListNode(ndata);
  if (tail_ == NULL) {
    head_ = newNode;
    tail_ = newNode;
    newNode->next = NULL;
    newNode->prev = NULL;
  }
  else {
    newNode->prev = tail_;
    newNode->next = NULL;
    tail_->next = newNode;
    tail_ = newNode;
  }
  length_++;
}

template <typename T>
void List<T>::print(std::ostream& os) const {
    for(const ListNode *it = head_; it != nullptr; it = it->next) {
        os << "Node: " << it->data << std::endl;
    }
}

template <typename T>
void List<T>::reverse() {
  reverse(head_, tail_);
}

int main() {

    List<int> my_list;
    for(int i = 0; i < 10; i++) {
        my_list.insertBack(i);
    }

    std::cout << "Before reverse:" << std::endl;
    my_list.print();
      
    my_list.reverse();

    std::cout << "After reverse:" << std::endl;
    my_list.print();

    
    return 0;
}