链表实现以及其相关链表操作

前言：

欢迎各位访问我的个人博客： www.guokangjie.cn

1、节点定义

主要分为 两部分：

1. 下一个节点
2. 当前节点的数据
3. 这里没有使用private修饰两个属性，是为了之后的使用时不必使用set和get方法来访问

   class LinkNode{
       LinkNode next;
       String data;
       
       @Override
       public String toString() {
           return "LinkNode{" +
                   "next=" + next +
                   ", data=" + data +
                   '}';
       }
   }

2、定义单链表

2.1 链表的增加与长度计算

1. 链表的增加只需要从头节点遍历到尾节点，在未节点添加数据，即可!
2. 计算链表的长度同理也是如此遍历到最后一个节点，在此过程中记录长度即可
3. 注意点需要为该类指定唯一的头节点（该节点很重要）

package cn.gxm.linkedlist;



/**
 * @author GXM
 * @date 2019/3/31
 * 单链表的实现以及相关基本操作
 */
public class MyLinkList {
    /**
     * 唯一的头节点
     */
    private LinkNode head = null;

    /**
     * 增加节点
      * @param data  节点数据
     */
   public void add(int data){
       LinkNode newNode = new LinkNode();
       newNode.data = data;
       if (head == null){
           head = newNode;
           return;
       }

       LinkNode tmpNode = head;
       while( tmpNode.next != null ){
           tmpNode = tmpNode.next;
       }
       tmpNode.next = newNode;
   }

    /**
     * 得到链表的长度
     * @return
     */
   public int length(){
       int size = 0;
       LinkNode tmpNode = head;
       while (tmpNode != null){
           size ++ ;
           tmpNode = tmpNode.next;
       }
       return size;
   }
}

2.2 链表的删除与输出

1. 以下方法还是在之前的那个类中编写
2. 删除指定的数据节点，可以是传入一个节点去删除，也可以传入一个索引下表来删除（这里索引从0开始），都可以，思路都是遍历到该索引所在的位置节点，通过前一个节点指向当前节点的下一个节点，就把当前节点删除了!
3. 遍历就很简单了，疯狂遍历直到最后一个节点，每次数据节点信息即可!

/**
     * 根据下表删除指定的链表节点数据
     * @param index 需要删除节点的下表 (从0开始)
     * @return 是否成功
     */
   public boolean delete(int index){
       if (index <0 || index >= length()){
           return false;
       }

       //删除头节点
       if (index == 0){
           head = head.next;
       }
       int i = 1;
       //前一个节点
       LinkNode preNode = head;
       //当前节点
       LinkNode curNode = head.next;
       while (curNode != null){
           //匹配删除
           if(i == index){
               preNode.next = curNode.next;
               return true;
           }
           //不匹配继续遍历
           preNode = curNode;
           curNode = curNode.next;
           i++;
       }
       return false;
   }


    /**
     * 打印列表
     */
    public void printList(){
        LinkNode tmpNode = head;
        while (tmpNode != null){
            System.out.println(tmpNode.data);
            tmpNode = tmpNode.next;
        }
   }

2.3 链表的排序

1. 对链表排序(因为我这里节点信息存储的是int 所以直接比较大小 如果不是请按需处理)
2. 我这里采用冒泡排序的原理（排序方法很多 大家可以自行按需处理）

public void order(){
      // 第一层循环的节点
      LinkNode curNode = head;
      int end = 0;
      while (curNode != null){
          //第二层循环的节点1
          LinkNode oneNode = curNode;
          //第二层循环的节点2
          LinkNode twoNode = oneNode.next;
         while (twoNode != null){
              if(oneNode.data > twoNode.data){
                  // 互换
                  int data = oneNode.data;
                  oneNode.data = twoNode.data;
                  twoNode.data = data;
              }
              // 继续比较
              oneNode = twoNode;
              twoNode = twoNode.next;
          }
         end++;
         if(end == length() - 1){
             break;
         }
      }
  }

2.3.1 排序举例

考虑到我排序写的不是很好，所以这里我做一个测试，把之前排序的每一个步骤写出来.测试数据如下

MyLinkList myLinkList = new MyLinkList();
       myLinkList.add(4);
       myLinkList.add(6);
       myLinkList.add(2);
       myLinkList.add(1);
       myLinkList.add(0);

第一遍：4 2 1 0 6
第二遍：2 1 0 4 6
第三遍：1 0 2 4 6
第四遍：0 1 2 4 6

还是没有思路，请自行上网查找排序的思路!。。。。。

2.4 删除链表中重复的数据

第一种思路：大家自然而然的就想到了遍历该链表，比较每一个元素，再去删除，但是时间复杂度会很大

第二种思路：大家也能想到不能重复的话，map不就可以完成吗，但是增加了空间复杂度

我这里就以第二种方式来做说明

/**
    * 删除链表中重复的元素
    * @return
    */
  public boolean deleteDuplecate(){
      Hashtable<Integer,Integer> map = new Hashtable<Integer,Integer>();

      LinkNode preNode = head;
      LinkNode curNode = head;
      while (curNode !=null){
          if(!map.containsKey(curNode.data)){
              //  key  就是当前值 对于value 这里没有要求所以都可以无所谓
              map.put(curNode.data,1);
              //继续执行判断
              preNode = curNode;
          }else {
              // 该节点以存在  删除该重复节点(并且只需要改变前节点的next即可)
              preNode.next = curNode.next;
          }
          curNode = curNode.next;
      }

      return true;
  }

2.5 找出链表中倒数第k个元素

第一种思路： 得到链表的长度，再遍历到（n-k）个元素的位置不就ok了吗,但是得到链表长度需要遍历一边，再遍历一遍得到倒数第k个元素，这样需要遍历两次链表

第二种思路：如果从头至尾的方向从链表的某个元素开始，遍历k的元素正好到达链表结尾，那么这个元素就是我们需要的，但是这种方法大家想一下就能知道，在遍历每一个元素的时候，都需要向下遍历k个元素判断是否是末尾元素，其实效率也挺差的。

第三种思路：设置两个节点索引，两者距离相差k，知道后者到达尾节点，那么前者就是我们需要求得的元素，并且只需要遍历一边。

我这里就以比较好的第三种方式实现

 /**
  * 找出链表中倒数第k个元素
  * @param k  倒数第k个元素的下标
  * @return   对应的节点
  */
public LinkNode findReciprocalElem(int k){

    // 直接返回头节点
    if(k == length()){
        return head;
    }

    LinkNode oneNode = head;
    LinkNode twoNode = head;
    for (int i=0;i<k;i++){
        twoNode = twoNode.next;
    }

    // 长度超出
    if (twoNode == null){
        return null;
    }

    //直到 快的节点（twoNode）到达尾节点
    while (twoNode != null){
        oneNode = oneNode.next;
        twoNode = twoNode.next;
    }
    return oneNode;
}

2.6 实现链表的反转

思路：将每一个链表的next的位置改变即可，注意最后需要改变头节点，不然你只是再当前改变，头节点信息没有改变，以后在使用时就会出现问题！（处理方式就是对遍历到的每一个节点分 前、后、以及当前、三个节点记录后再处理）

代码如下：

 /**
  * 反转链表
  * 遍历到的每一个节点分 前、后、以及当前、三个节点记录后再处理
  */
public boolean resverseLinked(){
     LinkNode curNode = head;
     LinkNode preNode = null;
     LinkNode nextNode;
     while (curNode != null){
         nextNode = curNode.next;
         curNode.next = preNode;
         preNode = curNode;
         curNode = nextNode;
     }
     head = preNode;  //不要忘了改变头节点
     return true;
}

2.7 从尾到头输出单链表

第一种方式：相信大家能想到，反转链表后输出，但是遍历次数较多

第二种方式：使用递归，输出尾节点后再输出前面的节点

我这里就写第二种方式：

 /**
  * 从尾到头输出单链表,使用递归的方式
  */
public void resverseToPrint(LinkNode node){
    if(node.next == null){
        //到达尾节点输出
        System.out.println(node.data);
        return;
    }else {
        //没有到达尾节点，继续递归
        resverseToPrint(node.next);
        // 上一次的结果以输出，可以输出这次的了
        System.out.println(node.data);
    }
}

因为该方法需要传入一个头节点，所以测试代码我这里给一下:

LinkNode head = new LinkNode();
       head.data = 1;
       LinkNode sec = new LinkNode();
       sec.data = 2;
       LinkNode thr = new LinkNode();
       thr.data = 3;
       LinkNode fou = new LinkNode();
       fou.data = 4;

       head.next = sec;
       sec.next = thr;
       thr.next = fou;

       myLinkList.resverseToPrint(head);

2.8 寻找单链表中的中间节点

第一种方式：先遍历得到链表长度，在根据长度判断遍历到中间节点
第二种方式: 设置连个节点，但twoNode的速度是oneOnde遍历速度的一倍

说明如下：

 /**
  *  寻找单链表中的中间节点
  * @return
  */
public LinkNode[] searchMidNode(){
    LinkNode []result = new LinkNode[2];
    LinkNode oneNode = head;
    LinkNode twoNode = head;
    while (oneNode != null){
        if(twoNode.next == null){
            result[0] = oneNode;
            return result;
        }
        if (twoNode.next.next == null){
            // 其实这里还有  oneNode.next
            result[0] = oneNode;
            result[1] = oneNode.next;
            return result;
        }
        oneNode = oneNode.next;
        twoNode = twoNode.next.next;
    }
    return null;
}

---

总结

1 . 以上是部分链表的操作，关于代码的测试，我仅仅是测试了一遍，如果有错误，希望各位可以指出，非常感谢!!
2 . 部分代码的逻辑判断不是很严谨只是考虑了大多数情况！并没有做出很好的判断