Last active
May 22, 2017 06:44
-
-
Save small-yellow-rice/c5e55242191614a7daecf57866ca9a8a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.NoSuchElementException; | |
| // singly linkedlist | |
| class LinkedList { | |
| class Node { | |
| private int val; | |
| private Node next; | |
| public Node(int value, Node nextNode) { | |
| val = value; | |
| next = nextNode; | |
| } | |
| } | |
| // head points to 1st element | |
| private Node head; | |
| // tail points to last element | |
| private Node tail ; | |
| private int size; | |
| // Constructor | |
| public LinkedList() { | |
| head = null; | |
| tail = null; | |
| size = 0; | |
| } | |
| // get the size of linkedlist | |
| public int getSize() { | |
| return size; | |
| } | |
| // append val to the tail of list | |
| public void append(int val) { | |
| Node newNode = new Node(val, null); | |
| if(head == null) { | |
| head = newNode; | |
| tail = head; | |
| } else { | |
| tail.next = newNode; | |
| tail = newNode; | |
| } | |
| size++; | |
| } | |
| // remove tail | |
| public void removeTail() { | |
| if(size == 0) throw new NoSuchElementException(); | |
| if(size == 1) { | |
| head = null; | |
| tail = null; | |
| } else { | |
| Node fast = head; | |
| Node slow = null; | |
| while (fast != tail) { | |
| slow = fast; | |
| fast = fast.next; | |
| } | |
| tail = slow; | |
| tail.next = null; | |
| } | |
| size--; | |
| } | |
| public void removeLarger(int target) { | |
| Node fakeHead = new Node(-1, head); | |
| Node workNode = head; | |
| Node prevNode = fakeHead; | |
| while(workNode != null) { | |
| // move workNode to the first node which <=target | |
| while(workNode != null && workNode.val > target) { | |
| workNode = workNode.next; | |
| } | |
| // remove nodes larger than target if found any | |
| prevNode.next = workNode; | |
| // when workNode is null, tail shoud be updated | |
| if(workNode == null) { | |
| if(prevNode == fakeHead) { | |
| tail = null; | |
| } else { | |
| tail = prevNode; | |
| } | |
| } | |
| // move prevNode and workNode | |
| prevNode = workNode; | |
| if(workNode != null) { | |
| workNode = workNode.next; | |
| } | |
| } | |
| head = fakeHead.next; | |
| fakeHead.next = null; | |
| } | |
| // print list | |
| public void printLst() { | |
| Node workNode = head; | |
| while(workNode != null) { | |
| System.out.print(workNode.val); | |
| if(workNode.next != null) System.out.print("->"); | |
| workNode = workNode.next; | |
| } | |
| System.out.println(); | |
| } | |
| } | |
| // test | |
| public class SinglyLinkedList { | |
| public static void main(String[] args) { | |
| LinkedList list = new LinkedList(); | |
| /* list.append(1); | |
| list.append(2); | |
| list.append(3); | |
| list.printLst(); | |
| list.removeLarger(100); | |
| list.printLst();*/ | |
| /* list.append(1); | |
| list.append(2); | |
| list.append(20); | |
| list.append(3); | |
| list.printLst(); | |
| list.removeLarger(19); | |
| list.printLst();*/ | |
| /* list.append(1); | |
| list.append(2); | |
| list.append(20); | |
| list.append(21); | |
| list.printLst(); | |
| list.removeLarger(19); | |
| list.printLst(); | |
| */ | |
| list.append(11); | |
| list.append(12); | |
| list.append(20); | |
| list.append(21); | |
| list.removeLarger(9); | |
| list.append(1); | |
| list.printLst(); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment