Exercises

1.

Write the splice function for a Linked List (with size and tail). The other list should end up completely empty.

You may assume both lists have at least one node.

2.

Write the sliceInHalf function for a Linked List (with size and tail). It should split the list into two halves. The first half should remain in this list, and the second half should be returned as a new list. If there are an odd number of nodes, the extra node should go in the second half.

🔗

You may assume the list has at least two nodes.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import LinkedList;

#include <iostream>
using namespace std;
^^^^
          
template<typename T>
LinkedList<T> LinkedList<T>::sliceInHalf() {
  // Write your code here
}
===!
template<typename T>
void LinkedList<T>::clear() {
  // placeholder implementation
}

template<typename T>
void LinkedList<T>::insertEnd(const T& value) {
  ListNode<T>* current = new ListNode<T>(value);
  if (size == 0) {
    head = current;
  } else {
    tail->next = current;
  }
  tail = current;
  size++;
}

void buildTestIntList(LinkedList<int>& list) {
  list.insertEnd(5);
  list.insertEnd(6);
  list.insertEnd(2);
  list.insertEnd(4);
}

TEST_CASE("LL/Split") {
  LinkedList<int> test_list;
  buildTestIntList(test_list); // 5, 6, 2, 4

int startNodeCount = ListNode<int>::nodeCount;

LinkedList<int> second_half = test_list.sliceInHalf();

REQUIRE(test_list.size == 2);
  REQUIRE(second_half.size == 2);

REQUIRE(test_list.tail->data == 6);
  REQUIRE(test_list.tail->next == nullptr);

REQUIRE(second_half.head->data == 2);
  REQUIRE(second_half.tail->data == 4);

REQUIRE(startNodeCount - ListNode<int>::nodeCount == 0);
}

TEST_CASE("LL/SplitLonger") {
  LinkedList<int> test_list;
  buildTestIntList(test_list);
  test_list.insertEnd(50);
  test_list.insertEnd(50); // 5, 6, 2, 4, 50, 50

LinkedList<int> second_half = test_list.sliceInHalf();

REQUIRE(test_list.size == 3);
  REQUIRE(second_half.size == 3);

REQUIRE(test_list.tail->data == 2);
  REQUIRE(test_list.tail->next == nullptr);

REQUIRE(second_half.head->data == 4);
  REQUIRE(second_half.tail->data == 50);
}

TEST_CASE("LL/SplitOddSize") {
  LinkedList<int> test_list;
  buildTestIntList(test_list);
  test_list.insertEnd(50); // 5, 6, 2, 4, 50

LinkedList<int> second_half = test_list.sliceInHalf();

REQUIRE(test_list.size == 2);
  REQUIRE(second_half.size == 3);

REQUIRE(test_list.tail->data == 6);
  REQUIRE(test_list.tail->next == nullptr);

REQUIRE(second_half.head->data == 2);
  REQUIRE(second_half.tail->data == 50);
}

Hint 1.

You will need to walk a pointer to just before the midpoint of the list. That should be (size / 2) - 1 steps from the start of the list.

🔗

Hint 2.

Both lists won’t necessarily end up with size = (size / 2). That is how long the first list should end up. Use the length of it to calculate the length of the second list.

🔗

For example, after splitting a list of 5 things, the original list should have (5 / 2) = 2 things and the new second list should have 3 things.

🔗

3.

Write the recursive reverseToString function for the Simple Linked List used in this chapter.

🔗

For a list containing nodes with values 10, 20, and 30, the function should return the string "30 20 10".

🔗

Loops have been intentionally disabled.

🔗

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"

import SimpleLinkedList;

#include <iostream>
using namespace std;

#define for "NoForLoops"
#define while "NoWhileLoops"
#define goto "NoGoto"
^^^^
          
string reverseToStringHelper(ListNode* node) {
    // Write your code here
}
string SimpleLinkedList::reverseToString() {
    // Call non-member recursive function and return the result
    string result = reverseToStringHelper(head);
    return result;
}
===!

#undef for
#undef while
#undef goto

void buildTestIntList(SimpleLinkedList& list) {
  list.insertStart(30);
  list.insertStart(20);
  list.insertStart(10);
}

TEST_CASE("LL/recursiveReverseToString") {
  SimpleLinkedList test_list;
  buildTestIntList(test_list); // 10, 20, 30

string result = test_list.reverseToString();
  INFO("Expected: |30 20 10|");
  INFO("Actual: |" << result << "|");
  REQUIRE(result == "30 20 10");

test_list.insertStart(5); // 5, 10, 20, 30
  result = test_list.reverseToString();
  INFO("Expected: |30 20 10 5|");
  INFO("Actual: |" << result << "|");
  REQUIRE(result == "30 20 10 5");
}

🔗

4.

Write the recursive getMaxValue function for the Simple Linked List used in this chapter.

🔗

You do not need to worry about what to do if the list is empty.

🔗

Loops have been intentionally disabled.

🔗

Welcome to Programming and Data Structures

Exercises 28.13 Exercises

1.

2.

3.

4.