Description
3.Programming [40 pt]
Make sure to write your name and BU ID in a comment at the top of the program,
along with your collaborator’s name and BU ID, if any. To use the compiler on the lab
computers, run “module load gcc” first. Submit only ListNode.h.
a) [20 pt] In this problem, you will implement insertion sort for singly linked list.
You are given two files: ListNode.h and Problem3a.cpp. Your job is to implement
the insertionSortList method in ListNode.h. The Problem3a.cpp file is given as a
sample test program for your implementation. You can compile with the test
program using:
> g++ -std=c++11 (-o myProgram) Problem3a.cpp
b) Recall Floyd’s cycle-detection algorithm that we went over in class.
• [10 pt] Implement this algorithm in the detectCycle method in the same
ListNode.h file. Similar to part a), you are given a sample test program
Problem3b.cpp to test your code. You can compile with the test program
using:
> g++ -std=c++11 (-o myProgram) Problem3b.cpp
• [10 pt] It turns out that you can modify Floyd’s algorithm to find the
node where the cycle starts as well (if one exists). Implement the
findCycleStart method in ListNode.h. You can also test this using
Problem3b.cpp.
Hint: Think about the distance from the cycle start node to the node
where the two points meet (say this is d). Think about the distances
(both non-loopy and loopy parts) the two pointers have traversed
respectively until they meet and their relationship to d.