Skip to content

Instantly share code, notes, and snippets.

@sidsbrmnn

sidsbrmnn/LinkedList.java

Last active July 21, 2020 16:21
Show Gist options
  • Save sidsbrmnn/4181968152b53f355413e35c81d46cd5 to your computer and use it in GitHub Desktop.
Save sidsbrmnn/4181968152b53f355413e35c81d46cd5 to your computer and use it in GitHub Desktop.
Download ZIP
Linked list operations in Java
Raw
LinkedList.java
public class LinkedList {
private Node head;
public LinkedList() {
}
public LinkedList(Node head) {
this.head = head;
}
public LinkedList(LinkedList list) {
this.head = list.getHead();
}
private Node getMiddleNode(Node head) {
Node result = head;
if (result != null) {
Node fast = head;
while (fast.next != null && fast.next.next != null) {
result = result.next;
fast = fast.next.next;
}
}
return result;
}
private Node merge(Node left, Node right) {
Node result;
if (left == null) {
result = right;
} else if (right == null) {
result = left;
} else {
if (left.value < right.value) {
result = left;
result.next = merge(left.next, right);
} else {
result = right;
result.next = merge(left, right.next);
}
}
return result;
}
private Node reverse(Node head) {
Node result;
if (head == null || head.next == null) {
result = head;
} else {
result = reverse(head.next);
head.next.next = head;
head.next = null;
}
return result;
}
private Node sort(Node head) {
Node result;
if (head == null || head.next == null) {
result = head;
} else {
Node middle = getMiddleNode(head);
Node nextToMiddle = middle.next;
middle.next = null;
Node left = sort(head);
Node right = sort(nextToMiddle);
result = merge(left, right);
}
return result;
}
public void append(int value) {
if (head == null) {
head = new Node(value);
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(value);
}
}
public void append(Node node) {
if (head == null) {
head = node;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
}
public void append(LinkedList list) {
if (head == null) {
head = list.getHead();
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = list.getHead();
}
}
public Node getHead() {
return head;
}
public boolean isEmpty() {
return head == null;
}
public void prepend(int value) {
if (head == null) {
head = new Node(value);
} else {
head = new Node(value, head);
}
}
public void prepend(Node node) {
if (head != null) {
Node current = node;
while (current.next != null) {
current = current.next;
}
current.next = head;
}
head = node;
}
public void prepend(LinkedList list) {
if (head != null) {
Node current = list.getHead();
while (current.next != null) {
current = current.next;
}
current.next = head;
}
head = list.getHead();
}
public void removeFirst() {
if (head != null) {
head = head.next;
}
}
public void reverse() {
head = reverse(head);
}
public void sort() {
head = sort(head);
}
@Override
public String toString() {
StringBuilder result = new StringBuilder();
if (head != null) {
Node current = head;
while (current.next != null) {
result.append(current.value).append(" -> ");
current = current.next;
}
result.append(current.value);
}
return result.toString();
}
}
Raw
Node.java
public class Node {
int value;
Node next;
Node() {
}
Node(int value) {
this.value = value;
}
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment