package pers.ty.$1101datastructure;
import java.util.Hashtable;
/**
 * @author Administrator
 * 實現單鏈表的基本操作,增加刪除節(jié)點、排序、打印、計算長度
 */
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個節(jié)點
   * @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
   * 中存在，則可以刪除
   * 優(yōu)點：時間復雜度低  缺點：需要額外的存儲空間來保存已訪問過得數據
   */
  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;
    }
  }
  /**
   * 從鏈表中刪除重復數據的第二種方法
   * 雙重循環(huán)遍歷
   * 優(yōu)缺點很明顯
   */
  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個節(jié)點
   * @return 該節(jié)點
   * 設置兩個指針p1、p2，讓p2比p1快k個節(jié)點，同時向后遍歷，當p2為空，則p1為倒數第k個節(jié)點
   */
  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鏈表的頭節(jié)點
   */
  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+" ");
    }
  }
  /**
   * 查詢單鏈表的中間節(jié)點
   * 定義兩個指針，一個每次走一步，一個每次走兩步...
   * @param head
   * @return q為中間節(jié)點
   */
  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;
  }
  /**
   * 在不知道頭指針的情況下刪除指定節(jié)點
   * 鏈表尾節(jié)點無法刪除，因為刪除后無法使其前驅節(jié)點的next指針置為空
   * 其他節(jié)點，可以通過交換這個節(jié)點與其后繼節(jié)點的值，然后刪除后繼節(jié)點
   * @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;
  }
  /**
   * 判斷兩個鏈表是否相交
   * 如果兩個鏈表相交，則肯定有相同的尾節(jié)點，遍歷兩個鏈表，記錄尾節(jié)點，看是否相同
   * @param h1鏈表1的頭節(jié)點
   * @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;
  }
  /**
   * 找出相交的第一個節(jié)點
   * @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();
  }
}