What is the f(n) runtime of the following pseudocode: sum-0 for A = N/2 downto 1 for B-1 t increment sum by B Explain: exactly w
1 answer:
You might be interested in
Answer:
removeDuplicates() function:-
//removeDuplicates() function removes duplicate elements form linked list.
void removeDuplicates() {
//declare 3 ListNode pointers ptr1,ptr2 and duplicate.
//initially, all points to null.
ListNode ptr1 = null, ptr2 = null, duplicate = null;
//make ptr1 equals to head.
ptr1 = head;
//run while loop till ptr1 points to second last node.
//pick elements one by one..
while (ptr1 != null && ptr1.next != null)
{
// make ptr2 equals to ptr1.
//or make ptr2 points to same node as ptr1.
ptr2 = ptr1;
//run second while loop to compare all elements with above selected element(ptr1->val).
while (ptr2.next != null)
{
//if element pointed by ptr1 is same as element pointed by ptr2.next.
//Then, we have found duplicate element.
//Now , we have to remove this duplicate element.
if (ptr1.val == ptr2.next.val)
{
//make duplicate pointer points to node where ptr2.next points(duplicate node).
duplicate = ptr2.next;
//change links to remove duplicate node from linked list.
//make ptr2.next points to duplicate.next.
ptr2.next = duplicate.next;
}
//if element pointed by ptr1 is different from element pointed by ptr2.next.
//then it is not duplicate element.
//So, move ptr2 = ptr2.next.
else
{
ptr2 = ptr2.next;
}
}
//move ptr1 = ptr1.next, after check duplicate elements for first node.
//Now, we check duplicacy for second node and so on.
//so, move ptr1 by one node.
ptr1 = ptr1.next;
}
}
Explanation:
Complete Code:-
//Create Linked List Class.
class LinkedList {
//Create head pointer.
static ListNode head;
//define structure of ListNode.
//it has int val(data) and pointer to ListNode i.e, next.
static class ListNode {
int val;
ListNode next;
//constructor to create and initialize a node.
ListNode(int d) {
val = d;
next = null;
}
}
//removeDuplicates() function removes duplicate elements form linked list.
void removeDuplicates() {
//declare 3 ListNode pointers ptr1,ptr2 and duplicate.
//initially, all points to null.
ListNode ptr1 = null, ptr2 = null, duplicate = null;
//make ptr1 equals to head.
ptr1 = head;
//run while loop till ptr1 points to second last node.
//pick elements one by one..
while (ptr1 != null && ptr1.next != null)
{
// make ptr2 equals to ptr1.
//or make ptr2 points to same node as ptr1.
ptr2 = ptr1;
//run second while loop to compare all elements with above selected element(ptr1->val).
while (ptr2.next != null)
{
//if element pointed by ptr1 is same as element pointed by ptr2.next.
//Then, we have found duplicate element.
//Now , we have to remove this duplicate element.
if (ptr1.val == ptr2.next.val)
{
//make duplicate pointer points to node where ptr2.next points(duplicate node).
duplicate = ptr2.next;
//change links to remove duplicate node from linked list.
//make ptr2.next points to duplicate.next.
ptr2.next = duplicate.next;
}
//if element pointed by ptr1 is different from element pointed by ptr2.next.
//then it is not duplicate element.
//So, move ptr2 = ptr2.next.
else
{
ptr2 = ptr2.next;
}
}
//move ptr1 = ptr1.next, after check duplicate elements for first node.
//Now, we check duplicacy for second node and so on.
//so, move ptr1 by one node.
ptr1 = ptr1.next;
}
}
//display() function prints linked list.
void display(ListNode node)
{
//run while loop till last node.
while (node != null)
{
//print node value of current node.
System.out.print(node.val + " ");
//move node pointer by one node.
node = node.next;
}
}
public static void main(String[] args) {
//Create object of Linked List class.
LinkedList list = new LinkedList();
//first we create nodes and connect them to form a linked list.
//Create Linked List 1-> 2-> 3-> 2-> 4-> 2-> 5-> 2.
//Create a Node having node data = 1 and assign head pointer to it.
//As head is listNode of static type. so, we call head pointer using class Name instead of object name.
LinkedList.head = new ListNode(1);
//Create a Node having node data = 2 and assign head.next to it.
LinkedList.head.next = new ListNode(2);
LinkedList.head.next.next = new ListNode(3);
LinkedList.head.next.next.next = new ListNode(2);
LinkedList.head.next.next.next.next = new ListNode(4);
LinkedList.head.next.next.next.next.next = new ListNode(2);
LinkedList.head.next.next.next.next.next.next = new ListNode(5);
LinkedList.head.next.next.next.next.next.next.next = new ListNode(2);
//display linked list before Removing duplicates.
System.out.println("Linked List before removing duplicates : ");
list.display(head);
//call removeDuplicates() function to remove duplicates from linked list.
list.removeDuplicates();
System.out.println("")
//display linked list after Removing duplicates.
System.out.println("Linked List after removing duplicates : ");
list.display(head);
}
}
Output:-
