[数据结构与算法]数据结构：LinkedList类和链表

1.前言

学前须知：

• 链表可分为很多种：是否有头、单双向、循环。
• 本文中所引用的大部分链表均是如下基本结构示意图（称：无头单向非循环链表）：
• 链表是一种物理存储上不连续的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
• 链表相对于上篇文章说到的顺序表优点主要在于：对数据的修改、更新、删除的时间复杂度可达到O(1)，对空间的占用也是比较小的（详细的对比放在本文后面）。

2.LinkedList主要的操作

在模拟实现ArrayList类之前，我们先要知道ArrayList类中有哪些主要操作，才能有针对性地对类中的这些方法进行模拟实现。

????????注意：这只是LinkedList类中最主要的几个操作，并不是全部操作，其他操作或多或少都有一些雷同，就不做过多的赘述。

3.模拟实现LinkedList

????????在模拟实现各种方法之前，需要先构建一个节点类出来，主要是用来为下面添加节点时候可以实例化出节点对象。其中，因为是链表，所以在类中需要有val（节点值）和next（用来指向下一个节点的地址），同时，还需要有一个构造方法来将输入的值做为节点的val值。

3.1 模拟实现add方法

add方法模拟实现有三种情况：一是头插法（在链表头部插入节点元素）；二是尾插法（在链表尾部插入节点）；三是指定下标插入法（在链表指定位置处插入节点元素）。

????????情况一：头插法。将新建节点的next指向头结点，然后再把自己赋为头节点即可。

    /**
     * 头插法
     * @param data
     */
    public void addFirst(int data){
        ListNode node=new ListNode(data);
        node.next=this.head;
        this.head=node;
    }

????????情况二：尾插法。将链表遍历到最后一个节点处，再把最后一个节点的next指向新建的节点即可；如若还未有节点插入链表，则直接将新建的节点赋为头节点即可。

    /**
     * 尾插法
     * @param data
     */
    public void addLast(int data){
        ListNode node=new ListNode(data);
        if(this.head==null){
            this.head=node;
        }else{
            ListNode cur=this.head;
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
    }

????????情况三：指定下标插入法。先判断index值的情况：（1）如若是小于0或者是大于链表长度的，则直接报错（越界访问）；（2）如若是等于0，则直接执行上面头插法的操作即可；（3）如若是等于链表的长度，则直接执行上面的尾插法即可；（4）如若是在0和链表长度之间的值，则先遍历链表执行next，次数为index-1次，这里，有人就会问“为什么是index-1次而不是index次呢？” – 因为我们将要把新建节点插入到index下标处，那么自然就要找到index下标的前一个节点，这样在后面操作中就可以非常顺利地将这个节点的next指向新建的节点，而如果直接找到是index下标的节点的话，则无法将新建节点插到这个节点之前（因为我们所建的是单向链表，只有next，双向链表会在后面再提到）。在理解完以上这些缘由之后，接下来就将新建节点的next指向之前找到的那个节点next指向的位置，最后将之前找到的节点的next指向新建的节点即可。

    /**
     * 判断查询是否越界
     * @param index
     */
    private boolean checkIndexAdd(int index){
        return index<0||index>size();
    }

    /**
     * 查找指定下标的前一个
     * @param index
     * @return
     */
    private ListNode findIndexSubOne(int index){
        ListNode cur=this.head;
        while(index-1>0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

    /**
     * 在指定位置处插入节点
     * @param index
     * @param data
     */
    public void addIndex(int index,int data){
        if(checkIndexAdd(index)){
            System.out.println("报错：越界访问");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode node=new ListNode(data);
        ListNode cur=findIndexSubOne(index);
        node.next=cur.next;
        cur.next=node;
    }

3.2 模拟实现remove方法

remove方法是找到链表中指定的值进行删除操作。

remove方法可分为两种情况：一是只删除链表中的第一个包含key值的节点；二是删除链表中所有包含key值的节点。
????????情况一：先判断头节点是否是空的，如若是空，则说明该链表是空的，无法删除指定的值；而如若头节点上的val值正好是想要删除的值，则直接将原头节点的下一个节点赋为头节点即可；如若都不是，那么直接从头开始遍历整个链表，直到找到为止，然后将所要删除节点的上一个节点的next指向所要删除节点的下一个节点即可；如若整个链表都遍历完还没有找到，那么说明链表中没有包含所要删除的节点。

    /**
     * 删除链表中的第一个包含key值的节点
     * @param key
     */
    public void remove(int key){
        if(this.head==null){
            System.out.println("链表为空");
            return;
        }
        if(this.head.val==key){
            this.head=this.head.next;
            return;
        }
        ListNode cur=this.head;
        while(cur.next!=null){
            if(cur.next.val==key){
                cur.next=cur.next.next;
                System.out.println("删除节点成功");
                return;
            }
            cur=cur.next;
        }
        System.out.println("链表中无此值");
    }

????????情况二：与前面类似的，需要先判断链表头节点是否是空的，如若是空的，则则说明该链表是空的，无法删除指定的值；与上面不一样的是，我们需要使用“双指针（前后指针法）”来对链表进行比遍历（前指针指向头节点的下一个节点，后指针指向头节点），如若前指针遇到的val值正好就是所要删除的值，则直接将后指针的next指向前指针的next即可，前指针再继续往前走，否则前后指针都一起往前走。最后，由于一直都是前指针再进行判断，所以就会发现头节点是没有被判断的，那么最后一步就需要对头节点进行判断，如若头节点的val值为所要删除的值，则将头节点的下一个节点赋为头节点，否则就不需要管他。

    /**
     * 删除链表中所有包含key值的节点
     * @param key
     */
    public void removeAllKey(int key){
        if(this.head==null){
            System.out.println("链表为空");
        }
        ListNode prev=this.head;
        ListNode cur=this.head.next;
        while(cur!=null){
            if(cur.val==key){
                prev.next=cur.next;
            }else{
                prev=cur;
            }
            cur=cur.next;
        }
        if(this.head.val==key){
            this.head=this.head.next;
        }
    }

3.3 模拟实现clear方法

clear方法是清除链表的所有节点操作。

????????（1）方法一：直接将头结点置为空，但是这样做时属于比较暴力的做法。

    /**
     * 清除链表中的所有节点
     */
    public void clear(){
        this.head=null;
    }

????????（1）方法二：将链表中头结点后面的节点一个一个置为空，最后再将头结点置为空。

    /**
     * 清除链表中的所有节点
     */
    public void clear(){
        ListNode cur=head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=null;
            cur=curNext;
        }
        head=null;
    }

4.八道关于链表操作的题目

4.1 第一题：反转链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

????????（1）如若链表头节点为空，则返回空即可。
????????（2）如若链表头节点的下一个节点为空，则说明该链表只有一个节点且为头节点，那么直接返回这个节点即可。
????????（3）将头节点的next指向null。
????????（4）使用前中后指针（三指针法）来将后节点（中指针）的next指向前节点（后指针），再将后指针变为中指针、中指针变为前指针、前指针变为前指针的下一个节点（next），循环此操作……直到中间指针为空停止，此时链表就被反转过来了，返回后指针即可。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
}

4.2 第二题：链表的中间节点

题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

????????（1）如若链表头节点为空，则返回空即可。
????????（2）使用前后指针即可。前指针每次前进两次，后指针每次前进一次，直到前指针为空时，返回后指针节点即是链表的中间节点。

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}

4.3 第三题：链表中倒数第k个节点

题目描述：输入一个链表，输出该链表中倒数第k个结点。

????????（1）如若k小于等于0，则返回空，因为倒数是没有负数的。
????????（2）如若链表头节点为空，则返回空即可。
????????（3）使用前后指针，让前指针先走k-1个单位，之后再前后指针一起走，直到前指针为空，后指针指向的节点就是倒数第k个节点。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k<=0){
            return null;
        }
        if(head==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(k-1>0){
            fast=fast.next;
            if(fast==null){
                return null;
            }
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

4.4 第四题：合并两个有序链表

题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

本题有多种常规的思路可以解决，这里使用其中一种：
????????（1）建立一个新的链表，然后分别遍历两个升序的链表，比较两个链表中节点val值的大小，将小的加入到新建的链表当中去，直到这两个链表中有一个遍历完。
????????（2）看谁遍历完，然后直接将没有遍历完的那个链表剩余的节点添加到新建的链表后面即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head=new ListNode();
        ListNode cur=head;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1==null){
            cur.next=list2;
        }else if(list2==null){
            cur.next=list1;
        }
        return head.next;
    }
}

4.5 第五题：链表分割

题目描述：现有一链表的头指针 ListNode* head，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

????????（1）如若链表头节点为空，则返回空即可。
????????（2）由于需要对链表进行分割，所以比较容易想到的方法是定义四个新的链表节点，将来分别用来存链表头节点、小于分割值最后节点、大于等于分割值最前节点、链表尾节点。
????????（3）遍历整个链表，将小于分割值的节点串在新建的链表头节点和小于分割值最后节点之间；将大于等于分割值的节点串在新建的大于等于分割值最前节点和链表尾节点之间。
????????（4）如若新建的链表头节点和小于分割值最后节点之间并没有节点存在，那么直接返回新建的大于等于分割值最前节点和链表尾节点之间的节点即可（就算这部分为空也没事，直接返回的是null）；否则，将小于分割值最后节点的next指向大于等于分割值最前节点，然后返回链表头节点即可。

public class Partition {
    public ListNode partition(ListNode head, int x) {
        // write code here
        if(head==null){
            return null;
        }
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=cur;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=as;
        if(as!=null){
            ae.next=null;
        }
        return bs;
    }
}

4.6 第六题：链表的回文结构

题目描述：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。

????????（1）如若链表头节点为空，则可以直接判断为不是回文链表。
????????（2）如若链表头节点的下一个节点为空，则说明该链表只有一个节点且为头节点，那么不管是如何看起，都是一样的，所以可直接判断为是回文链表。
????????（3）找到链表的中间节点。与上面思路一样，通过前后指针，前指针一次走两个单位，后指针一次走一个单位，直到前指针为空，后指针指向的节点就是链表的中间节点。
????????（4）对中间节点后的链表进行反转。与前面链表反转操作一样，将链表中间节点视为头节点，其他操作基本都是一样。
????????（5）从头尾指针分别往中间进行查找。如若头尾指针对应节点的val值是不一样的，那么直接判断其不是回文链表；如若头指针指向节点的下一个节点是尾指针指向的节点，那么可以直接判断其是回文链表；直到头尾指针相遇，则可以判断其是回文链表。

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here
        if(head==null){
            return false;
        }
        if(head.next==null){
            return true;
        }
        //第一步：先找到中间节点
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //第二步：对后半部分进行反转
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //从前后往中间进行查找
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
}

4.7 第七题：相交链表

题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

????????（1）如若有一个链表为空，则直接返回空即可，因为他们并没有公共的交点。
????????（2）遍历两个链表，分别得出两链表的长度，然后将较长的链表向前走两链表差个单位。
????????（3）将两链表每次一起前进1个单位，直到两链表对应的节点相同，这个节点就是链表相交的节点。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        int lenA=0;
        int lenB=0;
        ListNode pl=headA;
        ListNode ps=headB;
        while(pl!=null){
            lenA++;
            pl=pl.next;
        }
        while(ps!=null){
            lenB++;
            ps=ps.next;
        }
        pl=headA;
        ps=headB;
        int len=lenA-lenB;
        if(len<0){
            pl=headB;
            ps=headA;
            len=-len;
        }
        while(len>0){
            pl=pl.next;
            len--;
        }
        while(pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        return pl;
    }
}

4.8 第八题：环形链表

题目描述：给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。

????????（1）如若链表头节点为空，则判断这个链表不是环形链表。
????????（2）先使用快慢指针（前后指针），前指针每次前进两个单位，后指针每次前进一个单位，如果两个指针有指向共同的节点，那么这个链表就是环形链表；否则不是环形链表。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

环形链表拓展：查找进入环形链表的节点

题目描述：判断链表是否是环形链表，如若是，则返回进入环形链表的节点。

????????（1）如若链表头节点为空，则直接返回null。
????????（2）与上面判断环形链表类似的，先找出前后指针相交的节点。
????????（3）让后指针指回链表头节点，让前后指针每次都一起往前走一步，直到两指针相遇，则相遇的这个节点就是进入链表的节点。（下面画个图解释一下原因）

    /**
     * 查找进入环的节点
     * @return
     */
    public ListNode detectCycle(){
        if(this.head==null){
            return null;
        }
        ListNode slow=this.head;
        ListNode fast=this.head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null || fast.next==null){
            return null;
        }
        slow=this.head;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }

5.ArrayList（顺序表）和LinkedList（链表）的区别总结

6.后记

????????顺序表和链表的操作各有好坏，使用者只需根据自己的需要来进行使用即可。

????????本文所有代码都放在这里：链表代码，有需要的可以打开查看。