Set union

Linked list representation of a set

For this exercise, each set is represented by a linked list. A set is a collection of elements (in this case, characters) that never contains more than one occurrence of each element. Even though a linked list imposes an order on its elements, this order is not relevant when the collection is treated as a set. Therefore, the linked lists in this exercise are not ordered in any way. For example, the set {1, 2} may be represented with the linked list 1 -> 2, or by the linked list 2 -> 1. An empty linked list represents the empty set.

Problem statement

Write a Java program that, given two sets s1 and s2, modifies s1 to represent the union of s1 and s2 and modifies s2 to represent the empty set, where the union of two sets is the set containing all the elements that are in either s1, s2, or both. Remember that a set may not contain duplicated elements.

As shown in the test cases below, your code may assume that the two sets s1 and s2 are given as linked lists and that three additional reference variables p1, p2, and prev1 are declared. For this exercise, you may not declare any additional variables.

Make sure that your code works with all possible sets. The following 10 test cases are provided to help you test your code.