Java code as well as the runtime and space requirements using Big O Given a node

Question

Java code as well as the runtime and space requirements using Big O

Given a node in a linked list that looks like this: public class Node public int value; public Node next / +++This function should return true if the provided value is in the linked list. static boolean contains(Node head, int value) () /* This function should return true if all the values in the linked list are unique. Optimize for speed. static boolean checkUnique(Node head))h / This function should return true if all the values in the linked list are unique. Optimize for space do not use an auxiliary storage structure." static boolean checkUnique(Node head))h This function should insert the provided value into the sorted linked list provided. static void insertValue(Node head, int value) )

Explanation / Answer

1)

Here is code

static boolean contains(Node head, int value) {

Node temp = head;

boolean ans = false;

//search for our value till last node in linked list

while (temp!=null) {

if(temp.value == value) {

ans = true;

break;

}

temp = temp.next;

}

return ans;

}

Time Complexity O(n)

Sapce Complexity O(1)

2)

here is the code

static boolean checkUnique(Node head) {

Set<Integer> numbers = new HashSet<>();

Node temp = head;

boolean ans = true;

//traverse every node and check if it is present in set

while(temp!=null) {

if (!numbers.add(temp.value)) {

ans = false;

break;

}

temp = temp.next;

}

return ans;

}

Time Complexity O(n)

Sapce Complexity O(n)

3)

here is the code

static boolean checkUnique(Node head) {

Node temp = head;

Node temp2;

boolean ans = true;

//traverse every node

while(temp!=null && ans == true) {

temp2 = temp.next;

//check if remainder of linked list contains this node'value

while(temp2!=null) {

if ( temp.value == temp2.value) {

ans = false;

break;

}

temp2 = temp2.next;

}

temp = temp.next;

}

return ans;

}

Time Complexity O(n2)

Sapce Complexity O(1)

4)

static void insertValue(Node head, int value) {

Node prev = null, temp = head;

Node newNode = new Node();

newNode.value = value;

newNode.next = null;

while (temp!=null && temp.value < value) {

prev = temp;

temp = temp.next;

}

//smaller than head's value

if ( temp == head) {

newNode.next = head;

head = newNode;

}else {

newNode.next = prev.next;

prev.next = newNode;

}

}

Time Complexity O(n)

Sapce Complexity O(1)

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.