Main content:
Just upload the code, it's so unrestrained~~~
package pers.ty.$1101datastructure;import java.util.Hashtable;/** * @author Administrator * Implement the basic operations of single linked lists, adding deletion nodes, sorting, printing, and calculating length*/public class MyLinkedList { Node head = null;//The function of linked list headers/** Insert data into the linked list* @param d: the content of the insertion data*/ public void addNode(int d){ Node newNode=new Node(d); if(head==null){ head=newNode; return; } Node tmp=head; while(tmp.next!=null){ tmp=tmp.next; } //add Node to end tmp.next=newNode; } /** * @param index:Delete index node* @return returns true successfully, and returns false if failed */ public Boolean deleteNode(int index){ if(index<1||index>length()){ return false;//Delete the element position unreasonable} //Delete the first element in the linked list if(index==1){ head=head.next; return true; } int i=1; Node preNode=head; Node curNode=preNode.next; while(curNode!=null){ if(i==index){ preNode.next=curNode.next; return true; } preNode=curNode; curNode=curNode.next; i++; } return true; } /** * @return Return the length of the linked list length */ public int length(){ int length=0; Node tmp=head; while(tmp!=null){ length++; tmp=tmp.next; } return length; } /** * Sort the linked list* @return Return the sorted header node*/ public Node orderList(){ Node nextNode=null; int temp=0; Node curNode=head; while(curNode.next!=null){ nextNode=curNode.next; while(nextNode!=null){ if(curNode.data>nextNode.data){ temp=curNode.data; curNode.data=nextNode.data; nextNode.data=temp; } nextNode=nextNode.next; } curNode=curNode.next; } return head; } /** * Print all data in the linked list*/ public void printList(){ Node tmp=head; while(tmp!=null){ System.out.print(tmp.data+" "); tmp=tmp.next; } System.out.println(); } /** * The first way to delete data from the linked list* Traverse the linked list and store the traversed data into a Hashtable. During the traversal process, if the currently accessed value exists in the Hashtable *, you can delete it* Advantages: Low time complexity: Additional storage space is required to save the accessed data*/ public void deleteDuplecate1(){ Hashtable<Integer,Integer> table=new Hashtable<Integer,Integer>(); Node tmp=head; Node pre=null; while (tmp!=null) { if(table.containsKey(tmp.data)) pre.next=tmp.next; else{ table.put(tmp.data, 1); pre=tmp; } tmp=tmp.next; } } /** * The second way to delete duplicate data from the linked list* Double loop traversal* The advantages and disadvantages are obvious*/ public void deleteDuplecate2(){ Node p=head; while (p!=null) { Node q=p; while(q.next!=null){ if(p.data==q.next.data){ q.next=q.next.next; }else{ q=q.next; } } p=p.next; } } /** * @param k: Find the k-th until the last node in the linked list* @return This node* Set two pointers p1 and p2 to make p2 k faster than p1, and traverse backwards at the same time. When p2 is empty, p1 is the k-th until the last node*/ public Node findElem(Node head,int k){ if(k<1||k>this.length()) return null; Node p1=head; Node p2=head; for (int i = 0; i < k-1; i++) p2=p2.next; while (p2.next!=null) { p2=p2.next; p1=p1.next; } return p1; } /** * Implement the reversal of the linked list* @param head The head node of the linked list*/ public void reverseIteratively(Node head){ Node pReversedHead=head; Node pNode=head; Node pPrev=null; while (pNode!=null) { Node pNext=pNode.next; if(pNext==null) pReversedHead=pNode; pNode.next=pPrev; pPrev=pNode; pNode=pNext; } this.head=pReversedHead; } /** * Output a single linked list from the tail to the head by recursively* @param head */ public void printListReversely(Node head){ if(head!=null){ printListReversely(head.next); System.out.print(head.data+" "); } } /** * Query the intermediate node of a single linked list* Define two pointers, one step at a time and the other two steps at a time... * @param head * @return q is the intermediate node*/ public Node searchMid(Node head){ Node q=head; Node p=head; while (p!=null&&p.next!=null&&p.next.next!=null) { q=q.next; p=p.next.next; } return q; } /** * Delete the specified node without knowing the head pointer* The tail node of the linked list cannot be deleted because the next pointer of its predecessor node cannot be set to empty after deletion* Other nodes can exchange the values of this node and its successor node, and then delete the successor node* @param n * @return */ public boolean deleteNode(Node n){ if(n==null||n.next==null) return false; int tmp=n.data; n.data=n.next.data; n.next.data=tmp; n.next=n.next.next; return true; } /** * Determine whether two linked lists intersect* If two linked lists intersect, there must be the same tail node, traverse the two linked lists, record the tail nodes, and see if they are the same* @param h1 head node of linked list 1* @param h2 head node of linked list 2* @return whether they intersect*/ public boolean isIntersect(Node h1,Node h2){ if(h1==null||h2==null) return false; Node tail1=h1; while (tail1.next!=null){ tail1=tail1.next; } Node tail2=h2; while(tail2.next!=null){ tail2=tail2.next; } return tail1==tail2; } /** * Find the first node that intersects* @param h1 * @param h2 * @return */ public Node getFirstMeetNode(Node h1,Node h2){ if(h1==null||h2==null) return null; Node tail1=h1; int len1=1; while (tail1.next!=null){ tail1=tail1.next; len1++; } Node tail2=h2; int len2=1; while(tail2.next!=null){ tail2=tail2.next; len2++; } if(tail1!=tail2){ return null; } Node t1=h1; Node t2=h2; //Find out the longer linked list and go through if(len1>len2){ int d=len1-len2; while(d!=0){ t1=t1.next; d--; } } if(len1<len2){ int d=len2-len1; while(d!=0){ t2=t2.next; d--; } } while(t1!=t2){ t1=t1.next; t2=t2.next; } return t1; } public static void main(String[] args) { MyLinkedList list=new MyLinkedList(); }}The above is all the content of this article. I hope that the content of this article will be of some help to everyone’s study or work. I also hope to support Wulin.com more!