We define a redundant node in a singly-linked list to be a node w data value mat

Question

We define a redundant node in a singly-linked list to be a node w data value matches with the data value of a previous node in the list. In other words, given node node containing data value ai some node nodej (where i i) having data value d is redundant if hose di d. For example, consider the following linked list with one redundant node A zero indexed list in the form list 13, 4, 3, with a redundant node at index 2. Complete the distinct functiun in the rditor below. It has Curie paranneler: a Linkedi isINode, h referencing the first de linked list of integers. The function must return a LinkRdlistwode referen g the first node nfa list thatCOrtains only the non- redundant no des from the original list (and none of the redundant ones). All non-redundant nodes must be in the same exact order as they were in the original list. Input Format The first line oonlains an integrer, n, denpling line number of elements in list. Fach line inf the n subsequent lines (where si

Explanation / Answer

// Java program to remove duplicates from unsorted
// linked list

class LinkedList {

static Node head;

static class Node {

int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

/* Function to remove duplicates from an
unsorted linked list */
void remove_duplicates() {
Node ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;

/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;

/* Compare the picked element with rest
of the elements */
while (ptr2.next != null) {

/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {

/* sequence of steps is important here */
dup = ptr2.next;
ptr2.next = ptr2.next.next;
System.gc();
} else /* This is tricky */ {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}

void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}

public static void main(String[] args) {
LinkedList list = new LinkedList();
list.head = new Node(8);
list.head.next = new Node(3);
list.head.next.next = new Node(4);
list.head.next.next.next = new Node(3);
list.head.next.next.next.next = new Node(2);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next = new Node(1);
       list.head.next.next.next.next.next.next.next = new Node(2);
       list.head.next.next.next.next.next.next.next.next = new Node(6);

System.out.println("Linked List before removing duplicates : ");
list.printList(head);

list.remove_duplicates();
System.out.println("");
System.out.println("Linked List after removing duplicates : ");
list.printList(head);
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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