Assuming an IntNode class defined like this:
2.
3.
4.
5.
6.
7. }
1.
8.
9.
10.
11.
public String toString() {
return data + “”;
}
public class IntNode {
public int data;
public IntNode next;
public IntNode(int data, IntNode next) {
this.data = data; this.next = next;
Implement a method that will add a new integer before a target integer in the list. The method should return a pointer/reference to the front node of the resulting list. If the target is not found, it should return front without doing anything:
12. public static IntNode addBefore(IntNode
front, int target, int newItem) {
13. 14. 15.
/* COMPLETE THIS METHOD */
SOLUTION
}
public static IntNode addBefore(IntNode
front, int target, int newItem) {
16. 17.
target) { 18.
19.
20.
21.
22.
23.
24.
IntNode prev=null, ptr=front;
while (ptr != null && ptr.data !=
prev = ptr;
ptr = ptr.next;
}
if (ptr == null) { // target not found
return front;
}
IntNode temp = Intnew Node(newItem,
ptr); // next of new node should point to target
25. if (prev == null) { // target is first
item, so new node will be new front
26. return temp;
27. }
28. prev.next = temp;
29. return front; // front is unchanged
30. }
31. 32.
33.With the same IntNode class definition as above, implement a method that will add a new integer before the last item in a linked list. (In other words, the added integer will become the second-to- last item in the resulting linked list.) The method should return a pointer/reference to the front node of the resulting linked list. If the input linked list is empty, the method should return null, without doing anything.
34. public static IntNode addBeforeLast(IntNode
front, int item) {
35. 36. 37.
/* COMPLETE THIS METHOD */
38.
39.
40.
41.
42.
43.
44.
45.
46.
if (front == null) {
return null;
}
IntNode prev=null, ptr=front;
while (ptr.next != null) {
prev = ptr;
ptr = ptr.next;
}
SOLUTION
}
public static IntNode addBeforeLast(IntNode
front, int item) {
47. IntNode temp = Intnew Node(item,
ptr); // next of new node should point to last
48. if (prev == null) { // added item is
first, so new node will be new front
49. 50. 51. 52. 53. 54. 55.
return temp;
}
prev.next = temp;
return front; // front is unchanged
}
56.Given the following definition of a StringNode class: 57. public class StringNode {
58. 59. 60.
next) { 61.
62. 63. 64. 65. 66. 67.
public String data;
public StringNode next;
public StringNode(String data, StringNode
this.data = data; this.next = next;
}
public String toString() {
return data;
} }
Implement a method that will search a given linked list for a target
string, and return the number of occurrences of the target:
68. public static int
numberOfOccurrences(StringNode front, String
target) {
69. 70. 71.
/* COMPLETE THIS METHOD */
72.SOLUTION
}
73. public static int
numberOfOccurrences(StringNode front, String
target) {
74. int count=0;
75. for (StringNode ptr=front;ptr !=
null;ptr=ptr->next) {
76. 77. 78. 79. 80. 81.
if (target.equals(ptr.data)) {
count++;
}
return count;
}
82.* Assuming the IntNode class definition of problem 1, implement a method to delete EVERY OTHER item from an integer linked list. For example: before: 3->9->12->15->21
83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93.
after: 3->12->21
before: 3->9->12->15
after: 3->12
before: 3->9
after: 3
before: 3
after: 3
97. 98.
if (front == null) {
return;
If the list is empty, the method should do nothing.
public static void deleteEveryOther(IntNode front)
{
94. 95. 96.
SOLUTION
/* COMPLETE THIS METHOD */
}
public static void deleteEveryOther(IntNode
front) {
99. }
100.
101.
102.
103. 104.
Node prev=front, ptr=front.next;
boolean tbd=true;
while (ptr != null) {
if (tbd) {
ptr = ptr.next; // advance to
after item to be deleted
105. prev.next = ptr; // bypass
item to be deleted
106. tbd = false; // next item
should not be deleted
107. } else {
108. prev = ptr; // don’t
delete this (ptr) item, advance prev and ptr
109. ptr = ptr.next;
110. tbd = true;
next item for deletion
// but mark
111. 112. 113. 114.
} }
}
115.* With the same StringNode definition as in the previous problem, implement a method that will delete all occurrences of a given target string from a linked list, and return a pointer to the first node of the resulting linked list:
116. public static StringNode
deleteAllOccurrences(StringNode front, String
target) {
117. /* COMPLETE THIS METHOD */ 118. }
119.
SOLUTIONpublic static StringNode deleteAllOcurrences(StringNode front, String target) {
120.
121. if (front == null) {
122. return null;
123. }
124.
125. StringNode curr=front, prev=null;
126.
127. while (curr != null) {
128. if (curr.data.equals(target)) {
129. if (prev == null) { // target is the
first element
130.
131.
132.
133.
134.
135.
136.
137.
138. }
139.
140. return front;
141.}
142.
143.* Implement a (NON-RECURSIVE) method to find the common elements in two sorted linked lists, and return the common elements in sorted order in a NEW linked list. The original linked
front = curr.next;
} else {
prev.next = curr.next;
}
} else {
prev = curr;
}
curr = curr.next;
lists should not be modified. So, for instance,
>12->15->21
144. l2 = 2->3->6->12->19 145.
should produce a new linked list: 3->12 146.
l1 = 3->9-
You may assume that the original lists do not have any duplicate items.Assuming an IntNode class defined like this:
147. public class IntNode {
148. public int data;
149. public IntNode next;
150. public IntNode(int data, IntNode next) {
151. this.data = data; this.next = next;
152. }
153. public String toString() {
154. return data + “”;
155. }
156.
Complete the following method: // creates a new linked list consisting of the items common to the input lists
157. // returns the front of this new linked
list, null if there are no common items
158. public IntNode commonElements(IntNode
frontL1, IntNode frontL2) {
159. … 160. }
161.
SOLUTION
162. public IntNode commonElements(IntNode
frontL1, IntNode frontL2) {
163. 164.
null) { 165.
166. 167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
IntNode first=null, last=null;
while (frontL1 != null && frontL2 !=
if (frontL1.data < frontL2.data) {
frontL1 = frontL1.next
} else if (frontL1.data >
frontL2.data) {
frontL2 = frontL2.next;
} else {
IntNode ptr = new
IntNode(frontL1.data, null);
if (last != null) {
last.next = ptr;
} else {
first = ptr;
}
last = ptr;
177. 178. 179. 180. 181. 182. 183.
frontL1 = frontL1.next;
frontL2 = frontL2.next;
}
}
return first;
}