Skip to content

Instantly share code, notes, and snippets.

@fatihsokmen
Last active August 29, 2015 14:15
Show Gist options
  • Save fatihsokmen/3af3abb29971511977b0 to your computer and use it in GitHub Desktop.
Save fatihsokmen/3af3abb29971511977b0 to your computer and use it in GitHub Desktop.
Deleting a node from linked list 3-ways; using one pointer, two pointers and recursively
public class LinkedList {
private Node head = null;
public LinkedList() {
head = null;
}
public void add(int x) {
if (head == null) {
head = new Node(x);
} else {
Node c = head;
while (c.next != null) {
c = c.next;
}
c.next = new Node(x);
}
}
public void deleteUsingOnePointer(int x) {
if (head == null) {
return;
}
if (head.value == x) {
head = head.next;
return;
}
Node c = head;
while (c != null) {
if (c.next != null && c.next.value == x) {
c.next = c.next.next;
return;
} else {
c = c.next;
}
}
}
public void deleteUsingTwoPointers(int x) {
if (head == null) {
return;
}
Node p = null;
Node c = head;
while (c != null && c.value != x) {
p = c;
c = c.next;
}
if (p == null) {
head = head.next;
return;
} else if (c.value == x) {
p.next = c.next;
}
}
public void deleteRecursive(int x) {
if (head == null) {
return;
} else if (head.value == x) {
head = head.next;
} else {
head.next = deleteRecursiveInternal(head.next, x);
}
}
private Node deleteRecursiveInternal(Node n, int x) {
if (n == null) {
return null;
}
if (n != null && n.value == x) {
return n.next;
}
n.next = deleteRecursiveInternal(n.next, x);
return n;
}
public String toString() {
StringBuilder buffer = new StringBuilder();
Node c = head;
while (c != null) {
buffer.append(c.value).append(',');
c = c.next;
}
if (buffer.length() > 0){
buffer.delete(buffer.length() -1, buffer.length());
}
System.out.println(buffer.toString());
return buffer.toString();
}
private static class Node {
Node next;
int value;
public Node(int value) {
this.value = value;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment