CSE 326 Section I

Linked List

Karen Liu

4/6/00

TASK1:

a. Write a non-recursive function to reverse a singly linked list in O(N) time.

b. Write a function to reverse a singly linked list in O(N) time using constant extra space. (Create another list takes O(N) space)

c. Write a function to reverse the direction of pointers in a circular list.

TASK2:

a. Write a function to multiply two polynomials using linked list implementation.

b. Compare to the array implementation in the textbook, what are the cons and pros of different implementations.

TASK3:

a. Write routines to implement two stacks using only one array. Your stack should not declare an overflow unless every slot in the array is used. The data structure you create should be able to support basic stack operations: push, pop, top.

TASK4:

a. Write a function that searches for an integer, num, in a circularly linked list.

b. Write a function that deletes a node containing a number, num, from a circularly linked list. Your function should first search for num.

c. Write a function to concatenate two circular lists together. Assume that the pointer to each such list points to the last node. Your function should return a pointer to the last node of the concatenated circular list.

TASK5:

a. A palindrome is a word or phrase that is the same when spelled from the front or the back. For example, “reviver” and “Able was I ere I saw Elba” are both palindromes. We can determine if a word or phrase is a palindrome by using a stack. Write a function that returns true if the input string is a palindrome and false if it is not.