package pers.ty.$1101datastructure;import java.util.Hashtable;/** * @author Administrator * 實現單鏈表的基本操作,增加刪除節點、排序、打印、計算長度 */public class MyLinkedList {  Node head = null;//鏈表頭的作用  /**向鏈表中插入數據   * @param d：插入數據的內容   */  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:刪除第index個節點   * @return 成功返回true，失敗返回false   */  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;  }  /**   * @return 返回鏈表的長度length   */  public int length(){    int length=0;    Node tmp=head;    while(tmp!=null){      length++;      tmp=tmp.next;    }    return length;  }  /**   * 對鏈表進行排序   * @return 返回排序后的頭結點   */  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();  }  /**   * 從鏈表中刪除數據的第一種方法   * 遍歷鏈表，把遍歷到的數據存到一個Hashtable中，在遍歷過程中若當前訪問的值在Hashtable   * 中存在，則可以刪除   * 優點：時間復雜度低  缺點：需要額外的存儲空間來保存已訪問過得數據   */  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;    }  }  /**   * @param k：找到鏈表中倒數第k個節點   * @return 該節點   * 設置兩個指針p1、p2，讓p2比p1快k個節點，同時向后遍歷，當p2為空，則p1為倒數第k個節點   */  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;  }  /**   * 實現鏈表的反轉   * @param head鏈表的頭節點   */  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;  }  /**   * 通過遞歸從尾到頭輸出單鏈表   * @param head   */  public void printListReversely(Node head){    if(head!=null){      printListReversely(head.next);      System.out.print(head.data+" ");    }  }  /**   * 查詢單鏈表的中間節點   * 定義兩個指針，一個每次走一步，一個每次走兩步...   * @param head   * @return q為中間節點   */  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;  }  /**   * 在不知道頭指針的情況下刪除指定節點   * 鏈表尾節點無法刪除，因為刪除后無法使其前驅節點的next指針置為空   * 其他節點，可以通過交換這個節點與其后繼節點的值，然后刪除后繼節點   * @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;  }  /**   * 判斷兩個鏈表是否相交   * 如果兩個鏈表相交，則肯定有相同的尾節點，遍歷兩個鏈表，記錄尾節點，看是否相同   * @param h1鏈表1的頭節點   * @param h2鏈表2的頭結點   * @return 是否相交   */  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;  }  /**   * 找出相交的第一個節點   * @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;    //找出較長的鏈表先遍歷    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();  }}