Linked Lists - Advanced Topics in Java: Core Concepts in Data Structures - page 107

eXerCISeS 3

1. Write an instance method in the LinkedList class that returns true if the list is sorted in

ascending order and false otherwise.

2. Write an instance method to reverse the nodes of a linked list by creating a new list. the

method returns the newly created list.

3. Write a method to sort a linked list of integers as follows:

(a) Find the largest value in the list.

(b) delete it from its position and insert it at the head of the list.

(c) starting from what is now the second element, repeat (a) and (b).

(d) starting from what is now the third element, repeat (a) and (b).

Continue until the list is sorted.

4. Write a function that takes three arguments—a pointer to a linked list of integers and two

integers n and j —and inserts n after the j th element of the list. if j is 0 , n is inserted at the
head of the list. if j is greater than the number of elements in the list, n is inserted after the
last one.

5. the characters of a string are held on a linked list, one character per node.

(a) Write a method that, given a pointer to a string and two characters, c1 and c2 , replaces

all occurrences of c1 with c2 .

(b) Write a function that, given a pointer to a string and a character, c , deletes all

occurrences of c from the string. return a pointer to the modified string.

(c) Write a function that creates a new list consisting of the letters only in the given list, all

converted to lowercase and stored in alphabetical order. return a pointer to the new list.

(d) Write a function that, given pointers to two strings, returns true if the first is a substring

of the other and false otherwise.

6. Write a function that, given an integer n , converts n to binary and stores each bit in one node

of a linked list with the least significant bit at the head of the list and the most significant bit
at the tail. For example, given 13 , the bits are stored in the order 1 0 1 1 , from head to tail.
return a pointer to the head of the list.

7. Write a function that, given a pointer to a linked list of bits stored as in 6, traverses the list

once and returns the decimal equivalent of the binary number.

8. You are given two pointers, b1 and b2 . each points to a binary number stored as in question

6. You must return a pointer to a newly created linked list representing the binary sum of the
given numbers with the least significant bit at the head of the list and the most significant bit
at the tail of the list. Write functions to do this in two ways:

(i) Using the functions from 6 and 7

(ii) performing a “bit by bit” addition