Skip to content

Modified methods #2988

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 6 commits into from
Apr 3, 2022
Merged

Modified methods #2988

Changes from 2 commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
bb2a301
Modified methods
funCodeSonali Mar 23, 2022
02409a5
Merge branch 'master' into master
siriak Mar 30, 2022
5d44004
Modified SwapNodes(int , int) method
funCodeSonali Apr 3, 2022
529c88d
Merge remote-tracking branch 'origin/master'
funCodeSonali Apr 3, 2022
78cc268
Final SinglyLinkedList.java
funCodeSonali Apr 3, 2022
73be0c8
Merge branch 'master' into master
siriak Apr 3, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
293 changes: 158 additions & 135 deletions src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -44,16 +44,14 @@ public SinglyLinkedList(Node head, int size) {
public boolean detectLoop() {
Node currentNodeFast = head;
Node currentNodeSlow = head;
boolean flag = false;
while (currentNodeFast != null && currentNodeFast.next != null && currentNodeSlow != null && currentNodeSlow.next != null) {
while (currentNodeFast != null && currentNodeFast.next != null) {
currentNodeFast = currentNodeFast.next.next;
currentNodeSlow = currentNodeSlow.next;
if (currentNodeFast == currentNodeSlow) {
flag = true;
break;
return true;
}
}
return flag;
return false;
}

/**
Expand Down Expand Up @@ -109,15 +107,19 @@ public void swapNodes(int valueFirst, int valueSecond) {
*
*/
Node reverseList(Node node) {
Node prevNode = head;
while(prevNode.next!=node){
prevNode = prevNode.next;
}
Node prev = null, curr = node, next;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
node = prev;
return node;
prevNode.next = prev;
return head;
}

/**
Expand Down Expand Up @@ -161,6 +163,14 @@ public Node getHead() {
return head;
}

/**
* Set head of the list.
*
*/
public void setHead(Node head) {
this.head = head;
}

/**
* Calculate the count of the list manually
*
Expand Down Expand Up @@ -205,145 +215,41 @@ public String toString() {
return joiner.toString();
}

/**
* Driver Code
*/
public static void main(String[] arg) {
SinglyLinkedList list = new SinglyLinkedList();
assert list.isEmpty();
assert list.size() == 0 && list.count() == 0;
assert list.toString().equals("");

/* Test insert function */
list.insertHead(5);
list.insertHead(7);
list.insertHead(10);
list.insert(3);
list.insertNth(1, 4);
assert list.toString().equals("10->7->5->3->1");

/* Test search function */
assert list.search(10) && list.search(5) && list.search(1) && !list.search(100);

/* Test get function */
assert list.getNth(0) == 10 && list.getNth(2) == 5 && list.getNth(4) == 1;

/* Test delete function */
list.deleteHead();
list.deleteNth(1);
list.delete();
assert list.toString().equals("7->3");

assert list.size == 2 && list.size() == list.count();

list.clear();
assert list.isEmpty();

try {
list.delete();
assert false;
/* this should not happen */
} catch (Exception e) {
assert true;
/* this should happen */
}

Node instance = new Node();
Node head = new Node(0, new Node(2, new Node(3, new Node(3, new Node(4)))));
head = instance.deleteDuplicates(head);
instance.print(head);

}
}

/**
* This class is the nodes of the SinglyLinked List. They consist of a value and
* a pointer to the node after them.
*/
class Node {

/**
* Head refer to the front of the list
*/
public Node head;

/**
* Size of SinglyLinkedList
*/
public int size;



/**
* The value of the node
*/
int value;

/**
* Point to the next node
*/
Node next;

Node() {
}

/**
* Constructor
*
* @param value Value to be put in the node
*/
Node(int value) {
this(value, null);
}

/**
* Constructor
*
* @param value Value to be put in the node
* @param next Reference to the next node
*/
Node(int value, Node next) {
this.value = value;
this.next = next;
}

public Node deleteDuplicates(Node head) {
// sentinel
Node sentinel = new Node(0, head);
public void deleteDuplicates() {

// predecessor = the last node
// before the sublist of duplicates
Node pred = sentinel;

while (head != null) {
Node pred = head;
// predecessor = the node
// having sublist of its duplicates
Node newHead = head;
while (newHead != null) {
// if it's a beginning of duplicates sublist
// skip all duplicates
if (head.next != null && head.value == head.next.value) {
if (newHead.next != null && newHead.value == newHead.next.value) {
// move till the end of duplicates sublist
while (head.next != null && head.value == head.next.value) {
head = head.next;
while (newHead.next != null && newHead.value == newHead.next.value) {
newHead = newHead.next;
}
// skip all duplicates
pred.next = head.next;
pred.next = newHead.next;
newHead = null;

// otherwise, move predecessor
} else {
pred = pred.next;
}

// move forward
head = head.next;
pred = pred.next;
newHead = pred;
}
return sentinel.next;
}

public void print(Node head) {
public void print() {
Node temp = head;
while (temp != null && temp.next != null) {
System.out.print(temp.value + "->");
temp = temp.next;
}
if (temp != null) {
System.out.print(temp.value);
System.out.println();
}
}

Expand Down Expand Up @@ -379,20 +285,23 @@ public void insertNth(int data, int position) {
head = newNode;
size++;
return;
} else if (position == 0) {
}
if (position == 0) {
/* insert at the head of the list */
newNode.next = head;
head = newNode;
size++;
return;
}

Node cur = head;
for (int i = 0; i < position - 1; ++i) {
cur = cur.next;
}
newNode.next = cur.next;
cur.next = newNode;
size++;

}

/**
Expand All @@ -401,16 +310,38 @@ public void insertNth(int data, int position) {
*/
public void swapNodes(int a, int b) {
Node currentNode = head;
Node temp = null;
while (currentNode != null) {
if (currentNode.next.value == a) {
temp = currentNode.next;
Node prev_a , prev_b , a_node , b_node;
while(currentNode.next.value!=a&&currentNode.next.value!=b){
currentNode = currentNode.next;
}
if(currentNode.next.value==a){
prev_a = currentNode;
a_node = currentNode.next;

while(currentNode.next!=null&&currentNode.next.value!=b){
currentNode = currentNode.next;
}
if (currentNode.next.value == b) {
currentNode.next = temp;
prev_b = currentNode;
b_node = currentNode.next;
}
else{
prev_b = currentNode;
b_node = currentNode.next;
while(currentNode.next!=null&&currentNode.next.value!=a){
currentNode = currentNode.next;
}
currentNode = currentNode.next;
prev_a = currentNode;
a_node = currentNode.next;
}

if(a_node==null||b_node==null){
return;
}
Node c = a_node.next;
a_node.next = b_node.next;
b_node.next = c;
prev_a.next = b_node;
prev_b.next = a_node;
}

/**
Expand Down Expand Up @@ -479,4 +410,96 @@ public void checkBounds(int position, int low, int high) {
throw new IndexOutOfBoundsException(position + "");
}
}
/**
* Driver Code
*/
public static void main(String[] arg) {
SinglyLinkedList list = new SinglyLinkedList();
assert list.isEmpty();
assert list.size() == 0 && list.count() == 0;
assert list.toString().equals("");

/* Test insert function */
list.insertHead(5);
list.insertHead(7);
list.insertHead(10);
list.insert(3);
list.insertNth(1, 4);
assert list.toString().equals("10->7->5->3->1");
System.out.println(list.toString());
/* Test search function */
assert list.search(10) && list.search(5) && list.search(1) && !list.search(100);

/* Test get function */
assert list.getNth(0) == 10 && list.getNth(2) == 5 && list.getNth(4) == 1;

/* Test delete function */
list.deleteHead();
list.deleteNth(1);
list.delete();
assert list.toString().equals("7->3");
System.out.println(list.toString());
assert list.size == 2 && list.size() == list.count();

list.clear();
assert list.isEmpty();

try {
list.delete();
assert false;
/* this should not happen */
} catch (Exception e) {
assert true;
/* this should happen */
}

SinglyLinkedList instance = new SinglyLinkedList();
Node head = new Node(0, new Node(2, new Node(3, new Node(3, new Node(4)))));
instance.setHead(head);
instance.deleteDuplicates();
instance.print();

}

}

/**
* This class is the nodes of the SinglyLinked List. They consist of a value and
* a pointer to the node after them.
*/
class Node {

/**
* The value of the node
*/
int value;

/**
* Point to the next node
*/
Node next;

Node() {
}

/**
* Constructor
*
* @param value Value to be put in the node
*/
Node(int value) {
this(value, null);
}

/**
* Constructor
*
* @param value Value to be put in the node
* @param next Reference to the next node
*/
Node(int value, Node next) {
this.value = value;
this.next = next;
}

}