Linked List Exercises

Note All linked lists are null-terminated and singly linked. Input lists may be empty, unless otherwise stated. If new nodes may be created, then report whether or not space was exhausted, using a boolean reference parameter.

Answer each question with a C++ subroutine.

1. Insert in order Given a linked list of integers sorted from smallest (at the head end) to largest, and a pointer to a single node containing an integer, insert the node in the linked list so that it remains sorted. (solution)
2. Cumulative sum Given a null-terminated linked list, in, create a new null-terminated linked, list out, of the same length, such that node i of out contains the sum of the data in in's nodes up to and including node i of list in. Detect heap exhaustion and report it by setting a boolean variable. (solution)
3. Delete last node Given a nonempty list, delete the last node and set the new last link to null. (solution)
4. Deal Given a null terminated linked list, rearrange its nodes into two lists: <first node, third node, fifth node, ...> and <second node, fourth node, sixth node, ...>. Do not allocate any new nodes. (solution)
5. Rifle Shuffle Given two null terminated linked lists, combine their nodes so that the nodes of the new list alternate between those of the two original nodes: <first node of first list, first node of second list, second node of first list, second node of second list, ... >. Do not allocate any new nodes.
6. Catenate Given two null-terminated linked lists headed by left and right, set the last link of the left list to point to the right list, thus joining them into one list. Do not allocate any new nodes.
7. Reverse Given a null-terminated linked lists headed reverse the order of its nodes. Do not allocate any new nodes.
8. Read a list Given a nonnegative integer i, read i integers from the input and build a null-terminated linked list such that the first integer in the input is the first node and so forth. Detect heap exhaustion and report it by setting a boolean variable.
9. List to int Given a null-terminated linked list of integers from 0 to 9 (inclusive) representing a nonnegative integer in decimal (least significant digit at the head), compute into an unsigned variable, the integer that it represents. (The empty list represents 0.) You may assume that the list represents a number that can be represented by an unsigned.
10. Int to list Given an non-negative integer , create a null-terminated linked list of integers between 0 and 9 representing the integer (least significant digit first). (0 is represented by an empty list.) Set a boolean variable to indicate whether or not space has been exhausted. Hint. In C++ i/10, where i is an integer expression, gives the integer quotient of i divided by 10, and i%10 gives the remainder.