package pers.ty.
$1101datastructure
;
import java.util.Hashtable;
public
class
MyLinkedList {
Node head = null;
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;
}
tmp.next=newNode;
}
public
Boolean deleteNode(int index){
if
(index<1||index>length()){
return
false;
}
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;
}
public
int length(){
int length=0;
Node tmp=head;
while
(tmp!=null){
length++;
tmp=tmp.next;
}
return
length;
}
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;
}
public
void printList(){
Node tmp=head;
while
(tmp!=null){
System.out.
print
(tmp.data+
" "
);
tmp=tmp.next;
}
System.out.println();
}
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;
}
}
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;
}
}
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;
}
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;
}
public
void printListReversely(Node head){
if
(head!=null){
printListReversely(head.next);
System.out.
print
(head.data+
" "
);
}
}
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;
}
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;
}
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;
}
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;
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();
}
}