public class Node {

 //數(shù)據(jù)域
 public int data;
 //指針域，指向下一個節(jié)點
 public Node next;
 public Node() {
 }

 public Node(int data) {
 this.data = data;
 }

 public Node(int data, Node next) {
 this.data = data;
 this.next = next;
 }
}

 /**
 * 向鏈表添加數(shù)據(jù)
 *
 * @param value 要添加的數(shù)據(jù)
 */
 public static void addData(int value) {
 //初始化要加入的節(jié)點
 Node newNode = new Node(value);
 //臨時節(jié)點
 Node temp = head;
 // 找到尾節(jié)點
 while (temp.next != null) {
 temp = temp.next;
 }
 // 已經(jīng)包括了頭節(jié)點.next為null的情況了～
 temp.next = newNode;
 }

 /**
 * 遍歷鏈表
 *
 * @param head 頭節(jié)點
 */
 public static void traverse(Node head) {
 //臨時節(jié)點，從首節(jié)點開始
 Node temp = head.next;
 while (temp != null) {
 System.out.println("關注公眾號Java3y：" + temp.data);
 //繼續(xù)下一個
 temp = temp.next;
 }
 }

 /**
 * 插入節(jié)點
 *
 * @param head 頭指針
 * @param index 要插入的位置
 * @param value 要插入的值
 */
 public static void insertNode(Node head, int index, int value) {
 //首先需要判斷指定位置是否合法，
 if (index < 1 || index > linkListLength(head) + 1) {
 System.out.println("插入位置不合法。");
 return;
 }
 //臨時節(jié)點，從頭節(jié)點開始
 Node temp = head;
 //記錄遍歷的當前位置
 int currentPos = 0;
 //初始化要插入的節(jié)點
 Node insertNode = new Node(value);
 while (temp.next != null) {
 //找到上一個節(jié)點的位置了
 if ((index - 1) == currentPos) {
 //temp表示的是上一個節(jié)點
 //將原本由上一個節(jié)點的指向交由插入的節(jié)點來指向
 insertNode.next = temp.next;
 //將上一個節(jié)點的指針域指向要插入的節(jié)點
 temp.next = insertNode;
 return;
 }
 currentPos++;
 temp = temp.next;
 }
 }

 /**
 * 獲取鏈表的長度
 * @param head 頭指針
 */
 public static int linkListLength(Node head) {
 int length = 0;
 //臨時節(jié)點，從首節(jié)點開始
 Node temp = head.next;
 // 找到尾節(jié)點
 while (temp != null) {
 length++;
 temp = temp.next;
 }
 return length;
 }

 /**
 * 根據(jù)位置刪除節(jié)點
 *
 * @param head 頭指針
 * @param index 要刪除的位置
 */
 public static void deleteNode(Node head, int index) {
 //首先需要判斷指定位置是否合法，
 if (index < 1 || index > linkListLength(head) + 1) {
  System.out.println("刪除位置不合法。");
  return;
 }

 //臨時節(jié)點，從頭節(jié)點開始
 Node temp = head;
 //記錄遍歷的當前位置
 int currentPos = 0;
 while (temp.next != null) {
  //找到上一個節(jié)點的位置了
  if ((index - 1) == currentPos) {
  //temp表示的是上一個節(jié)點
  //temp.next表示的是想要刪除的節(jié)點
  //將想要刪除的節(jié)點存儲一下
  Node deleteNode = temp.next;
  //想要刪除節(jié)點的下一個節(jié)點交由上一個節(jié)點來控制
  temp.next = deleteNode.next;
  //Java會回收它，設置不設置為null應該沒多大意義了(個人覺得,如果不對請指出哦～)
  deleteNode = null;
  return;
  }
  currentPos++;
  temp = temp.next;
 }
 }

 /**
 * 對鏈表進行排序
 *
 * @param head
 *
 */
 public static void sortLinkList(Node head) {
 Node currentNode;
 Node nextNode;
 for (currentNode = head.next; currentNode.next != null; currentNode = currentNode.next) {
  for (nextNode = head.next; nextNode.next != null; nextNode = nextNode.next) {
  if (nextNode.data > nextNode.next.data) {
   int temp = nextNode.data;
   nextNode.data = nextNode.next.data;
   nextNode.next.data = temp;
  }
  }
 }
 }

 /**
 * 找到鏈表中倒數(shù)第k個節(jié)點(設置兩個指針p1、p2，讓p2比p1快k個節(jié)點，同時向后遍歷，當p2為空，則p1為倒數(shù)第k個節(jié)點
 *
 * @param head
 * @param k 倒數(shù)第k個節(jié)點
 */
 public static Node findKNode(Node head, int k) {
 if (k < 1 || k > linkListLength(head))
  return null;
 Node p1 = head;
 Node p2 = head;
 // p2比怕p1快k個節(jié)點
 for (int i = 0; i < k - 1; i++)
  p2 = p2.next;
 // 只要p2為null，那么p1就是倒數(shù)第k個節(jié)點了
 while (p2.next != null) {

  p2 = p2.next;
  p1 = p1.next;
 }
 return p1;
 }

 /**
 * 刪除鏈表重復數(shù)據(jù)(跟冒泡差不多，等于刪除就是了)
 *
 * @param head 頭節(jié)點
 */
 public static void deleteDuplecate(Node head) {
 //臨時節(jié)點，(從首節(jié)點開始-->真正有數(shù)據(jù)的節(jié)點)
 Node temp = head.next;

 //當前節(jié)點(首節(jié)點)的下一個節(jié)點
 Node nextNode = temp.next;
 while (temp.next != null) {
  while (nextNode.next != null) {
  if (nextNode.next.data == nextNode.data) {
   //將下一個節(jié)點刪除(當前節(jié)點指向下下個節(jié)點)
   nextNode.next = nextNode.next.next;
  } else {

   //繼續(xù)下一個
   nextNode = nextNode.next;
  }
  }
  //下一輪比較
  temp = temp.next;
 }
 }

 /**
 * 查詢單鏈表的中間節(jié)點
 */
 public static Node searchMid(Node head) {
 Node p1 = head;
 Node p2 = head;
 // 一個走一步，一個走兩步，直到為null，走一步的到達的就是中間節(jié)點
 while (p2 != null && p2.next != null && p2.next.next != null) {
  p1 = p1.next;
  p2 = p2.next.next;
 }
 return p1;
 }

 /**
 * 通過遞歸從尾到頭輸出單鏈表
 *
 * @param head 頭節(jié)點
 */
 public static void printListReversely(Node head) {
 if (head != null) {
  printListReversely(head.next);
  System.out.println(head.data);
 }
 }

 /**
 * 實現(xiàn)鏈表的反轉(zhuǎn)
 *
 * @param node 鏈表的頭節(jié)點
 */
 public static Node reverseLinkList(Node node) {
 Node prev ;
 if (node == null || node.next == null) {
  prev = node;
 } else {
  Node tmp = reverseLinkList(node.next);
  node.next.next = node;
  node.next = null;
  prev = tmp;
 }
 return prev;
 }