链表问题整理

链表可以说是最常见的数据结构之一。看似简单但是真正应用起来有很强的灵活性，现在将链表问题归纳一下，从链表的常见变式到具体应用，争取对链表问题一网打尽！

单链表

相比于数组插入删除时O(n)的时间复杂度，链表的时间复杂度只要O(1)

但是链表随机访问的性能没有数组好，需要 O(n) 的时间复杂度

尾部插入

private void insertToTail(int value){

       Node node =  new Node(value,null);
       if(null == head){
             head = node;
       }else {
           Node q = head;
           while(q.next!= null ){
                 q = q.next;
           }

           //关键步骤，不能调换顺序
           node.next = q.next;
           q.next = node;
       }

   }

索引插入

private void insert(int value,int index){
       Node node = head;
       Node preNode  = null;
       int pos = 0;
       while(node != null && index != pos){
          preNode = node;
           node = node.next;
           pos++;
       }

       Node newNode= new Node(value,node.next);
       if(node == null){
           return ;
       }
       if(preNode ==null){
           newNode.next = head;
           head = newNode;
       }else{
           newNode.next = preNode.next;
           preNode.next = newNode;
       }

   }

通过值删除节点

注意头节点的特殊处理

private void deleteByNode(int data){

       if(head == null){
           return ;
       }
       Node node = head;
       //应该是保存插入节点的上一个节点
       Node q = null;
       while(node!= null && node.data != data){
           //保存上一个节点
           q = node;
           //使得循环继续下去
           node = node.next;
       }

       //说明没有找到节点
       if(node == null){
           return;
       }

       //删除head头节点的时候，此时q依然为null(没有进入循环)，必须特殊处理，精髓所在
       if(q == null){
           head = head.next;
       }else{
           q.next = q.next.next;
       }
   }

通过值查找

private Node findByValue(int data){
       Node node = head;
       while(node != null){
           node = node.next;
       }
       return node;
   }

双链表

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

比如，删除操作的情况存在两种情况：

• 删除结点中“值等于某个给定值”的结点
• 删除给定指针指向的结点。

第一种情况链表的时间复杂度都是O(n)，第二种情况双链表无需查找，O(1)时间复杂度删除节点

LinkedHashMap用的就是双向链表

插入操作

以尾部插入举例

private void insertToTail(int data){
        DuoNode node = new DuoNode(data);
        DuoNode last = tail;
        if(count == 0){
            head = node;
            tail = node;

        }else{
            last.next = node;
            node.prev = last;
            tail = node;
        }
        ++count;
    }

删除操作

删除头部

private DuoNode deleteHead(){
        DuoNode h = head;
        if(count >0){
            //两句话最好不要反着来
            head = h.next;
            head.prev = null;
            --count;
        return h;
        }
        return null;
    }

删除尾部

private DuoNode deleteTail() {
       DuoNode q = tail;
       if (count > 0) {
           tail = tail.prev;
           tail.next = null;
           --count;
       }
       return q;
   }

查找

private DuoNode findIndex(int index) {
        if(index >count){
            return null;
        }
        DuoNode node = head;
        int num = 0;
        while(num < index) {
            node = node.next;
            ++num;
        }
            return node;
    }

循环链表

循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表

私有属性

public class CircleLinkedList {
    private Node head;
    private Node tail;
    private int count;

    CircleLinkedList(){
        head = null;
        tail = null;
        count = 0;
    }
    //...
}

插入操作

private void insertHead(int data){

       Node node = new Node(data,null);
       if(count== 0){
           head = node;
           tail = node;
       }else{
           node.next = head;
           tail.next = node;
           head = node;
           count++;
       }
   }

应用

LRU缓存淘汰算法

思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
   • 如果此时缓存未满，则将此结点直接插入到链表的头部；
   • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

构造方法

比起普通链表多维护一个容量

public class LRUByLinkedList{	
    private Node head;
    //最大容量
    private int size;
    //已存储容量
    private int count;

    public LRUByLinkedList(int capacity){
        head = null;
        size = capacity;
        count = 0;
    }
    //...
}

插入操作

private void insert(int data){
        Node preNode = findNode(data);
    //更新缓存，旧缓存清除
        if(null != preNode){
            delete(preNode);
        }else{
            if(count >= size){
                //如果缓存溢出，删除最早的缓存
                deleteToTail();
            }
        }
        insertToHead(data);
    }

查找缓存

private Node findNode(int data) {
        Node node = head;
        while(null != node && null != node.next){
            Node nextNode = node.next;
            if(data == nextNode.data){
                return node;
            }
            node = nextNode;
        }
        return  null;
    }

详细代码

单链表反转

递归法

• 注意开始边界条件

• 当递归的最后节点的时候将最后第二个节点的next节点指向最后第二个节点，然后最后一个节点成为了头节点

/**
     * 链表反转  ——递归法（精髓）
     * @param head
     * @return
     */
    public Node reverseList(Node node) {
        if (node == null || node.next == null) return node;
        Node p = reverseList(node.next);
        node.next.next = node;
        node.next = null;
        return p;
    }

非递归法

要点：1. 必须维护前驱节点 2. 反转将后继指针指向前驱节点

/**
 * 单链表反转
 * @param list
 * @return
 */
public static  Node reserve(Node list){
    Node cur = list;
    //存储链表的上一个节点，遍历完之后变成头节点
    Node pre = null;
    while(cur != null){
        //暂存指向下一个节点的引用
        Node next = cur.next;
        //反转，将存储的下一个节点指向上一个节点
        cur.next = pre;
        //下面两部将链表向下移动
        pre = cur;
        cur = next;
    }
    //遍历完之后pre变成头节点
    return pre;
}

环的检测

//使用快慢指针法。追及问题，只要慢指针追上快指针，说明存在环路
    public static boolean checkCircle(Node list){
        
        if(list== null)
        {
            return false;
        }

        Node fast = list.next;
        Node slow = list;
        //注意截止条件
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }

        return false;
    }

两个有序链表的合并

public static Node mergeSortList(Node la,Node lb){
            Node  p = la;
            Node q  =lb;
            Node head ;

            //处理头部的特殊情况
       if(p.data<q.data){
                head = p;
                p = p.next;
            }else{
                head = q;
                q = q.next;
            }
            Node r = head;

        while(q != null && p != null) {
            if (q.data < p.data) {
                r.next = q;
                q = q.next;
            } else {
                r.next = p;
                p = p.next;
            }
        }
        if(p.next == null){
            r.next = q;
        }

        if(q.next == null){
            r.next =p;
        }
        return r;
   }

可以通过维护一个哨兵让代码更加简洁

/**
 * 有序合并（哨兵机制优化）
 * @param la
 * @param lb
 * @return
 */

public static Node mergeTwoListsA(Node la,Node lb){
    Node soldier =  new Node(0,null);
    Node p = soldier;

    //正常的合并逻辑

    return p;

}

递归法

/**
   * 递归合并链表
   * @param l1
   * @param l2
   * @return
   */
      public Node mergeTwoLists(Node l1, Node l2) {
          if (l1 == null) {
              return l2;
          }
          else if (l2 == null) {
              return l1;
          }
          else if (l1.data < l2.data) {
              l1.next = mergeTwoLists(l1.next, l2);
              return l1;
          }
          else {
              l2.next = mergeTwoLists(l1, l2.next);
              return l2;
          }

      }

删除链表的倒数n个节点

快指针比慢指针前k个节点，然后快指针遍历到尾部的时候慢指针刚刚好到删除节点，注意保存删除节点的上一个节点

private  void deleteLastKth(Node list,int index){
        Node fast = list;
        //注意这里的i！！！！
        int i = 1;
        while(fast != null && i<index){
            fast = fast.next;
            i++;
        }
        if(fast == null){
            return ;
        }
        Node slow = list;
        Node prev = null;
        //遍历到最后fast指针指向最后一个节点，注意快慢指针之间的间隔
        //因为选择使用prev作为删除节点，所以next !=null
        while(fast.next != null){
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }

        if(prev != null){
            prev.next = prev.next.next;
        }else{
            list = list.next;
        }
        return ;
    }

求链表的中间节点

快慢指针法

private static Node fndMiddleNode(Node list ){
       Node fast = list;
       Node slow = list;

       //第一个条件是防止head为null，第二个是为了使得fast指针遍历到最后一个节点
       while(fast != null && fast.next != null){
           fast = fast.next.next;
           slow = slow.next;
       }

       return slow;
   }

判断是否回文串

思路：

使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。最后比较中点两侧的链表是否相等。

//使用的
public boolean isPalindrome(Node list){
        Node slow = list;
        Node fast = list;
        Node prev = null;

        if(list == null){
            return false;
        }
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            Node next = slow.next;
			//链表反向
            slow.next = prev;
            //前驱指针后移
            prev = slow;
            //慢指针后移
            slow = next;
        }
        //跨过中点，使得prev和slow同步，这里存在节点数是奇数还是偶数的情况
        if(fast != null){
            slow = slow.next;
        }
        if(slow != null){
            if(slow.data != prev.data){
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }