Java implements a variety of operations for single linked lists
- 2020-05-26 08:25:01
- OfStack
Main contents:
The basic operation of single linked list Delete duplicate data Find the next-to-last element, k Reverse the list Output the linked list from end to end Find the intermediate node Check if the list has a ring Deletes a specified node without knowing the header pointer How to determine if two lists intersect and find the intersection nodeDirectly on the code, is so bold ~~~
package pers.ty.$1101datastructure;
import java.util.Hashtable;
/**
* @author Administrator
* Realize the basic operation of single linked list , Add delete node, sort, print, calculate length
*/
public class MyLinkedList {
Node head = null;// The function of the chain header
/** Insert data into a linked list
* @param d : the content of the inserted 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 the first index A node
* @return Successfully returns true , failed to return false
*/
public Boolean deleteNode(int index){
if(index<1||index>length()){
return false;// The location of the deleted element is not reasonable
}
// Delete the first in the list 1 An element
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 Returns the length of the list length
*/
public int length(){
int length=0;
Node tmp=head;
while(tmp!=null){
length++;
tmp=tmp.next;
}
return length;
}
/**
* Sort the list
* @return Returns 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 the 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();
}
/**
* Deletes data from a list 1 methods
* Traversing a linked list saves the traversed data to 1 a Hashtable , if the currently accessed value is Hashtable
* , it can be deleted
* Pros: low time complexity Cons: extra storage space is required to hold 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;
}
}
/**
* Deletes the number of duplicates from the list 2 methods
* Double loop traversal
* The pros and cons 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 bottom of the list k A node
* @return The node
* Set two Pointers p1 , p2 And let p2 than p1 fast k The nodes are traversed backwards at the same time, when p2 Is empty, then p1 For the bottom first k A 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;
}
/**
* Reverse the list
* @param head The head node of a 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;
}
/**
* Recursively output a single linked list from end to end
* @param head
*/
public void printListReversely(Node head){
if(head!=null){
printListReversely(head.next);
System.out.print(head.data+" ");
}
}
/**
* Query the middle node of a single linked list
* Define two Pointers, 1 Every time a go 1 Step, 1 Take 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;
}
/**
* Deletes a specified node without knowing the header pointer
* The end node of a linked list cannot be deleted because it cannot make its precursor node after deletion next The pointer is set to null
* For other nodes, you can exchange the value of this node with its successor nodes, and then delete the successor nodes
* @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 if two lists intersect
* If two lists intersect, there must be the same tail node. Walk through the two lists, record the tail node, and see if they are the same
* @param h1 The list 1 The head of the node
* @param h2 The list 2 The head of the node
* @return Whether the intersection
*/
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 intersection 1 A node
* @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 a longer list to traverse first
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();
}
}