int listLength(ListNode headNode){
int length = 0;
ListNode currentNode = headNode;
while(currentNode != null){
length++;
currentNode=currentNode.getNext();
}
return length;
}
ListNode InsertInLinkedList(ListNode headNode, ListNode nodeToInsert, int position){
if (headNode == null) {
return nodeToInsert;
}
int length = listLength(headNode);
if (position > length+1 || position<1) {
return nodeToInsert;
}
if(position == 1){
nodeToInsert.setNext(headNode);
return nodeToInsert;
}else{
ListNode previousNode = headNode;
int count = 1;
while(count < position-1){
previousNode = previousNode.getNext();
count++;
}
ListNode currentNode = previousNode.getNext();
nodeToInsert.setNext(currentNode);
previousNode.setNext(nodeToInsert);
}
return headNode;
}
ListNode DeleteNodeFromLinkedList(ListNode headNode, int position){
int size = listLength(headNode);
if (position > size+1 || position <1) {
System.out.println("输入的删除位置超出聊表范围");
return headNode;
}
if(position == 1){
ListNode currentNode = headNode.getNext();
headNode =null;
return currentNode;
}else{
ListNode previousNode = headNode;
int count = 1;
while(count < position){
previousNode = previousNode.getNext();
count++;
}
ListNode currentNode = previousNode.getNext();
previousNode.setNext(currentNode.setNext());
currentNode = null;
}
return headNode;
}
void DeleteLinkedList(ListNode headNode){
ListNode auxilaryNode, iterator = head;
while (iterator != null) {
auxilaryNode = iterator.getNext();
iterator = null;
iterator = auxilaryNode;
}
}
DDLNode DDLInsert(DDLNode headNode, DDLNode nodeToInsert, int position){
if (headNode == null) {
return nodeToInsert;
}
int size = getDDLLength(headNode);
if (position > size+1 || position <1) {
System.out.println("输入的参数有误！插入位置的大小为1~"+ (size+1) );
return headNode;
}
if (position == 1) {
nodeToInsert.setNext(headNode);
headNode.setPrevious(nodeToInsert);
return nodeToInsert;
}else{
DDLNode previousNode = headNode;
int count = 1;
while(count < position-1){
previousNode = previousNode.getNext();
count++;
}
DDLNode currentNode = previousNode.getNext();
nodeToInsert.setNext(currentNode);
if(currentNode != null){
currentNode.setPrevious(nodeToInsert);
}
previousNode.setNext(nodeToInsert);
nodeToInsert.setPrevious(previousNode);
}
return headNode;
}
void DeleteNodeFromDDL(DDLNode headNode, int position){
int size = getDDLLength(headNode);
if (position >size || position < 1) {
System.out.println("输入的删除位置超出了表范围，正确的参数范围为：1~"+ size);
return headNode;
}
if (position == 1) {
DDLNode currentNode = headNode.getNext();
headNode = null;
currentNode.setPrevious(null);
return currentNode;
}else{
DDLNode previousNode = headNode;
int count = 1;
while(count < position-1){
previousNode = previousNode.getNext();
count++;
}
DDLNode currentNode = previousNode.getNext();
DDLNode laterNode = currentNode.getNext();
previousNode.setNext(laterNode);
if (laterNode != null) {
laterNode.setPrevious(previousNode);
}
currentNode = null;
}
return headNode;
}
int getCircularLinkedListLength(CLLNode headNode){
int length = 0;
CLLNode currentNode = headNode;
while(currentNode != null){
length++;
currentNode = currentNode.getNext();
if (currentNode == headNode) {
break;
}
}
return length;
}
void printCircularLinkedList(CLLNode headNode){
CLLNode CLLNode = headNode;
while(CLLNode != null){
System.out.print(CLLNode.getData()+"->");
CLLNode = CLLNode.getNext();
if (CLLNode == headNode) {
break;
}
}
System.out.println("(" + CLLNode.getData() + ")headNode");
}
void InsertAtEndOfCLL(CLLNode headNode, CLLNode nodeToInsert){
CLLNode currentNode = headNode;
while (currentNode.getNext() != headNode) {
currentNode.setNext(currentNode.getNext());
}
if (headNode == null) {
headNode = nodeToInsert;
}else{
nodeToInsert.setNext(headNode);
currentNode.setNext(nodeToInsert);
}
}
void DeleteFrontNodeFromCLL(CLLNode headNode){
CLLNode auxilaryNode = headNode;
CLLNode currentNode = headNode;
if (headNode == null) {
System.out.println("List is empty");
return;
}
while(currentNode.getNext() != headNode){
currentNode.setNext(currentNode.getNext());
}
headNode = auxilaryNode.getNext();
currentNode.setNext(headNode);
auxilaryNode = null;
return;
}
ListNode NthNodeFromEnd(ListNode head, int NthNode){
ListNode pTemp = head, pNthNode = null;
for (int count = 1; count < NthNode, count++){
if(pTemp != null){
pTemp = pTemp.getNext();
}
}
while(pTemp != null){
if (pNthNode == null) {
pNthNode = head;
}else{
pNthNode = pNthNode.getNext();
}
pTemp = pTemp.getNext();
}
if (pNthNode != null) {
return pNthNode;
}
return null;
}
int getLoopLengthIfExistsLoop(ListNode head){
ListNode slowPtr = head, fastPtr = head;
boolean loopExists = false;
int counter = 0;
if (head == null) {
return 0;
}
while(slowPtr.getNext() != null && fastPtr.getNext().getNext() != null){
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext().getNext();
if (slowPtr == fastPtr) {
loopExists=true;
break;
}
}
if (loopExists) {
fastPtr = fastPtr.getNext();
while(fastPtr != slowPtr){
fastPtr = fastPtr.getNext();
counter++;
}
return counter;
}
return 0;
};
ListNode insertIntoSortedList(ListNode head, ListNode newNode){
if (head == null) {
return newNode;
}
ListNode currentNode = head, auxilaryNode = head;
while (currentNode != null && currentNode.getData() < newNode.getData()) {
auxilaryNode = currentNode;
currentNode = currentNode.getNext();
}
newNode.setNext(currentNode);
auxilaryNode.setNext(newNode);
return head;
}
ListNode FindIntersectingNode(ListNode list1, ListNode list2){
int L1 = 0, L2 = 0, diff = 0;
ListNode head1 = list1, head2 = list2;
while(head1 != null){
L1++;
head1 = head1.getNext();
}
while(head2 != null){
L2++;
head2 = head2.getNext();
}
if (L1 < L2) {
head1 = list2;
head2 = list1;
diff = L2 - L1;
}else{
head1 = list1;
head2 = list2;
diff = L1 - L2;
}
for (int i = 0; i<diff; i++) {
head1 = head1.getNext();
}
while (head1 != null && head2 != null) {
if (head1 == head2) {
return head1;
}
head1 = head1.getNext();
head2 = head2.getNext();
}
return null;
}
ListNode FindMiddleNode(ListNode head){
ListNode ptr1x = head, ptr2x = head;
int i = 0;
while(ptr2x != null){
if (i == 0) {
ptr2x = ptr2x.getNext();
i = 1;
}
if (i == 1) {
ptr2x = ptr2x.getNext();
ptr1x = ptr1x.getNext();
i = 0;
}
}
return ptr1x;
}
ListNode IsLinkedListLengthEven(ListNode head){
while(head != null && head.getNext() != null){
head = head.getNext().getNext();
}
if (head == null) {
return 0;
}else{
return 1;
}
}
ListNode MergeList(ListNode a, ListNode b){
ListNode result = null;
if (a == null) {
return b;
}
if (b == null) {
return a;
}
if (a.getData() <= b.getData()) {
result = a;
result.setNext(MergeList(a.getNext(), b));
}else{
result = b;
result.setNext(MergeList(a, b.getNext()));
}
}
public class ArrayStack{
private int top;
private int capacity;
private int[] array;
public ArrayStack(){
capacity = 1;
array = new int[capacity];
top = -1;
}
public boolean isStackEmpty(){
return (top == -1);
}
public int isStackFull(){
return (top == capacity-1);
}
public void push(int data){
if (isStackFull(S)) {
System.out.println("Stack is full!");
return;
}
array[++top] = data;
}
public int pop(){
if (isStackEmpty(S)) {
System.out.println("Stack is empty!");
return 0;
}
return array[top--];
}
public deleteStack{
top = -1;
}
}
public class DynArraystack{
private int[] array;
private int top;
private int capacity;
public DynArraystack(){
top = -1;
capacity = 1;
array = new int[capacity];
}
public boolean isStackEmpty(){
return (top == -1);
}
public boolean isStackFull(){
return (capacity-1 == top);
}
public void push(int data){
if(isStackFull(S)){
doubleStack(S);
}
array[++top] = data;
}
private void doubleStack(){
int[] newArray = new int[capacity*2];
System.arraycopy(array,0,newArray,0,capacity);
capacity = capacity*2;
array = newArray;
}
public void pop(){
if (isStackEmpty) {
System.out.println("StackOverflow");
}else return (array[top--]);
}
public void deleteStack(){
top = -1;
}
}
public class LLStack{
private LLNode headNode;
public LLStack(){
this.headNode = new LLNode(null);
}
public void push(int data){
if (headNode == null) {
headNode = new LLNode(data);
}else if(headNode.getData() == null){
headNode.setData(data);
}else{
LLNode llNode = new LLNode(data);
llNode.setNext(headNode);
headNode = llNode;
}
}
public int top(){
if (headNode = null) {
return null;
}else{
return headNode.getData();
}
}
public int pop(){
if (headNode == null) {
throw new StackEmptyException("StackEmpty");
}else{
int data = headNode.getData();
headNode = headNode.getNext();
return data;
}
}
public boolean isStackEmpty(){
if (headNode == null) {
return true;
}else return false;
}
public void deleteStack(){
headNode = null;
}
}
public class AdvancedStack implements Stack{
private Stack elementStack = new LLStack();
private Stack minStack = new LLStack();
public void push(int data){
elementStack.push(data);
if (minStack.isEmpty() || (Integer)minStack.top() > (Integer(data))) {
minStack.push(data);
}else{
minStack.push(minStack.top());
}
}
public int pop(){
if (elementStack.isEmpty()) {
return 0;
}
minStack.pop();
return elementStack.pop();
}
public int getMinimum(){
return minStack.top();
}
public int top(){
return elementStack.top();
}
public boolean isEmpty(){
return elementStack.isEmpty();
}
}
public class AdvancedStack implements Stack{
private Stack elementStack = new LLStack();
private Stack minStack = new LLStack();
public void push(int data){
elementStack.push(data);
if (minStack.isEmpty() || (Integer)data < (Integer)minStack.top()) {
minStack.push(data);
}
}
public int pop(){
if(elementStack.isEmpty()){
return 0;
}
if (elementStack.top() == minStack.top()) {
minStack.pop();
}
return elementStack.pop();
}
}
boolean isHuiwen(String inputStr){
char[] inputChar = inputChar.toCharArray();
Stack s = new LLStack();
int i = 0;
while(inputChar[i] != 'X'){
s.push(inputChar[i]);
i++;
}
i++;
while(i < inputChar.length){
if (s.isEmpty) {
return false;
}
if (inputChar[i] != ((Character)s.pop()).charValue) {
return false;
}
i++;
}
return true;
}
public class ArrayTwoStack{
private int[] dataArray;
private int topOne;
private int topTwo;
private int size;
public ArrayTwoStack(int size){
if (size < 2) {
throw new IllegalStateException("size < 2 is not persmissable!");
}
dataArray = new int[size];
this.size = size;
topOne = -1;
topTwo = size
}
public void push(int StackID, int data){
if (topTwo == topOne+1) {
throw new StackOverflowException("Stack is full!");
}
if (StackID == 1) {
dataArray[++topOne] = data;
}else if (StackID == 2) {
dataArray[--topTwo] = data;
}else return;
}
public int pop(int StackID){
if (StackID ==1) {
if (topOne == -1) {
throw new StackEmptyException("First Stack is empty!");
}
int toPop = dataArray[topOne];
dataArray[topOne--] = null;
return toPop;
}
if (StackID ==2) {
if (topTwo == this.size) {
throw new StackEmptyException("First Stack is empty!");
}
int toPop = dataArray[size];
dataArray[topTwo++] = null;
return toPop;
}
}
public int top(int StackID){
if (StackID == 1) {
if (topOne == -1) {
throw new StackEmptyException("First Stack is empty!")
}else{
return dataArray[topOne];
}
}else if (StackID == 2) {
if (topTwo == this.size) {
throw new StackEmptyException("Second Stack is empty!")
}else {
return dataArray[topTwo];
}
}else return null;
}
public boolean isEmpty(int StackID){
if (StackID == 1) {
return (topOne == -1);
}else if (StackID == 2) {
return (topTwo == this.size);
}else return true;
}
}
public class StackSorter{
public static Stack sort(Stack s){
LLStack s = new LLStack();
if () {
}
}
}