Lab Assignment 2: Linked lists
1.
For a given singly linked list insert a node:
a. at the beginning
b. at the end
c. at a given position k
2.
For a given singly linked list delete a node:
a. at the beginning
b. at the end
c. at a given position
3.
Reverse a singly linked list.
Input: 1 -> 2 -> 5 -> 7 -> 4 -> NULL
Output: 4 -> 7 -> 5 -> 2 -> 1 -> NULL
4.
Print the sum of all even numbers stored in a linked list.
5.
Print all the elements at the index of multiples of k with the first element assumed to have an index of
0. Do this for a single pass of the linked list.
Input:
k=3
12 -> 15 -> 18 -> 17 -> 19 -> 20 -> 22 -> NULL
Output:
12 -> 17 -> 22 -> NULL
6.
Delete duplicate elements from a given linked list. Retain the earliest entries.
Input:
20 -> 18 -> 15 -> 20 -> 6 -> 18 -> 5 -> 3 -> NULL
Output:
20 -> 18 -> 15 -> 6 -> 5 -> 3 -> NULL
7.
Reverse a linked list in groups of given size.
Input:
k=4
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 12 -> 7 -> NULL
Output:
4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> 7 -> 12 -> NULL
8.
Remove in a linked list all the nodes that have a greater value to their right. Input:
10 -> 12 -> 15 -> 20 -> 5 -> 16 -> 25 -> 8 -> NULL
10 -> 12 -> 15 -> 20 -> 25 -> 26 -> 30 -> 40 -> NULL
20 -> 18 -> 15 -> 10 -> 8 -> 6 -> 5 -> 3 -> NULL Output:
20 -> 25 -> 8 -> NULL
40 -> NULL
20 -> 18 -> 15 -> 10 -> 8 -> 6 -> 5 -> 3 -> NULL
9.
Remove alternate nodes from a given linked list.
Input:
20 -> 18 -> 15 -> 10 -> 8 -> 6 -> 5 -> 3 -> NULL Output:
20 -> 15 -> 8 -> 5 -> NULL
10. Perform pair-wise swapping of nodes of a given linked list.
Input:
20 -> 18 -> 15 -> 10 -> 8 -> 6 -> 5 -> 3 -> 7 -> NULL
Output:
18 -> 20 -> 10 -> 15 -> 6 -> 8 -> 3 -> 5 -> 7 -> NULL
11. Check whether a given singly linked list is palindrome or not.
Input:
a -> b -> NULL a -> b -> a ->
NULL s -> a -> g -> a -> r ->
NULL r -> a -> d -> a -> r ->
NULL Output:
not palindrome
palindrome not
palindrome
palindrome
12. Calculate the frequency of occurrence of each element in a given linked list in the same order they
appear. Avoid printing multiple entries.
Input:
20 -> 18 -> 15 -> 20 -> 6 -> 18 -> 5 -> 18 -> NULL
Output:
Freq(20) = 2
Freq(18) = 3
Freq(15) = 1
Freq(6) = 1
Freq(5) = 1
13. Make a function that adds a linked list to itself at the end.
Input:
4 -> 2 -> 1 -> NULL Output:
4 -> 2 -> 1 -> 4 -> 2 -> 1 -> NULL
14. Write a program to represent a polynomial in variable X using a singly linked list, each node of which
contains two kinds of data fields; one to store coefficient and another stores the power on variable X.
For example, if a polynomial is: P(X) = 2X^2 + 3X + 4 then the structure of linked list is as below:
+------+------+
+------+------+
+------+------+
|
2 | 2
| -> | 3
| 1
| -> |
4 | 0
|
+------+------+
+------+------+
+------+------+
Perform polynomial addition on two such polynomials represented by linked lists and generate a
new list representing the sum of those polynomials.
Input:
+------+------+
+------+------+
|
2 | 2
| -> | 3
| 1
| ->
+------+------+
+------+------+
+------+------+
+------+------+
|
1 | 3
| -> | 2
| 1
| ->
+------+------+
|
4 | 0
| -> NULL
+------+------+
+------+------+
|
1 | 0
| -> NULL
+------+------+
+------+------+
+------+------+ Output:
+------+------+
+------+------+
+------+------+
+------+------+
|
1 | 3
| -> | 2
| 2
| -> |
5 | 1
| -> |
5 |
0 | -> NULL
+------+------+
+------+------+
+------+------+
+------+------+
15. Create a linked list in which each node has two pointers: FRIEND and NEXT. FRIEND can point to any
other node in the linked list. Make a duplicate linked list with the same values and connections.
Input: (original linked list)
5 -> 1; 1 -> 4; 4 -> 2; 2 -> 5; 5 -> 5
________________________
|
___________ |
___________
|
|
| |
|
|
|
v
| v
|
v
+------+
+------+
+------+
+------+
+------+
|
5 | -> |
4 | -> |
1 | -> |
2 | -> |
5 | -> NULL
+------+
+------+
+------+
+------+
+------+
^
|
^
|
|
|________________________|
|
|_______________________________________________|
Output: (new linked list)
5 -> 1; 1 -> 4; 4 -> 2; 2 -> 5; 5 -> 5
