单链表的基本操作

目录

一、什么是单链表？

二、顺序表和链表的比较：

1.空间性能的比较：

2.时间性能的比较：

三、单链表的实现和基本操作

1.实现单链表节点以及初始化头结点

2.获取当前链表中元素的数量

3.获取指定位置的节点

4.获取指定位置的元素

5.在尾部添加结点元素

6.在指定位置添加元素

7.删除指定位置的元素

四、反转链表

1.用反转头实现 

2.用递归实现反转链表

五、用快慢指针获取链表中的值

1.快慢指针获取链表中间的值

2.通过快慢指针获取倒数第k个结点值

六、循环链表

1.通过快慢指针判断链表是否有环

2.通过快慢指针以及第三个指针获取环的入口元素

七、约瑟夫问题

一、什么是单链表？

链表的存储结构在逻辑上、概念上的连续结构，但在实际的物理存储上是非连续、非顺序的。

它的存储单元以结点为单位，每一个结点由数据域和指针域两个域组成。数据域存储数据元素信息data，指针域存储直接后继存储位置next。

整个链表的存取必须从头指针开始进行，头指针指链表中第一个结点（即第一个数据元素的存储映像，也称首元结点）的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个结点的指针为空（null）。

头指针有两种情况：

（1）为了方便处理，在单链表的第一个结点（首元结点）之前附设一个结点，称为头节点，头节点一般不放数据，所以data = null；

（2）将第一个存放数据的节点（首元结点）的指针作为头指针。

二、顺序表和链表的比较：

1.空间性能的比较：

（1）存储空间的分配：

顺序表是用数组实现的，存储空间必须预先分配，元素个数扩充受一定的限制，容易造成存储空间浪费或空间溢出现象。而链表不需要为它预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。

因此，当线性表的长度变化较大，难以预估存储规模时，适合采用链表作为存储结构。

（2）存储密度的大小：

存储密度=数据元素本身占用的存储量 / 结点结构占用的存储量

链表要存储数据域和指针域，所以存储密度小于1；顺序表只存储数据，所以存储密度为1；

因此，当线性表的长度变化不大，提前知道其大小的时候，为节约存储空间，适合采用顺序表（数组）作为存储结构。

2.时间性能的比较：

（1）查找元素的效率：

顺序表是由数组实现的，存储位置连续，有下标索引，所以查找取值操作顺序表时间复杂度为O(1)

链表是逻辑上的连续，物理上不连续，查找元素只能从表头开始依次向后遍历链表，所以链表时间复杂度为O(n)。

（2）插入和删除操作的效率：

对于链表，插入和删除只需要修改指针，不涉及元素的移动，所以时间复杂度为O(1)。

对于顺序表，插入和删除涉及到后面元素的移动，所以时间复杂度为O（n）。

三、单链表的实现和基本操作

1.实现单链表节点以及初始化头结点

//单向链表的实现以及基本操作
public class MySingleLinkedList {
    //节点类设计，设计结点内部类
    private class Node{
        T item;//结点存储的数据
        Node next;//下一个结点的地址
        //节点类设计
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
 
    //成员变量
    Node head;//存储链表的起始位置
    int size;//记录链表中的元素数量
 
    //构造方法初始化头结点
    public MySingleLinkedList() {
        //将头部结点进行初始化
        this.head = new Node(null,null);
        //将size初始化
        this.size = 0;
    }
}

2.获取当前链表中元素的数量

  //获取当前链表中元素的数量
    public int size(){
        return this.size;
    }

3.获取指定位置的节点

    //获取指定位置的节点
    //思路：从链表首元结点开始（头结点后第一个结点）依次往后遍历，
    //     直到到达目标元素位置，将结点返回。
    public Node getNode(int pos){
        //当传入的值为-1时，就return头结点。一般在0结点插入时会出现此情况。
        if (pos == -1){
            return this.head;
        }
        //获取0位置的元素
        Node target = this.head.next;
        //通过遍历找到指定的位置的元素
        for(int i = 0;i
            target = target.next;
        }
        //返回结果
        return target;
    }

4.获取指定位置的元素

  //获取指定位置的元素
    //思路：用getNode（）方法获取目标结点，然后返回结点元素
    public T get(int pos){
        return getNode(pos).item;
    }

5.在尾部添加结点元素

//在尾部添加结点元素
    //思路：如果链表没有元素，直接将头结点的指针指向添加元素，
    //     如果链表已有元素，先到达尾结点，再将尾结点指针指向添加元素。
    public void add(T t){
        //创建插入的结点
        Node node = new Node(t,null);
        if (this.size == 0){
            //size == 0说明链表还没有元素，直接将头节点指针指向插入节点
            this.head.next = node;
        }else {
            //size != 0，先找到尾结点，再插入
            this.getNode(size - 1).next = node;
        }
        //将链表中结点的数量加1
        this.size++;
    }

6.在指定位置添加元素

//在指定位置添加元素
    //思路：先获取到指定位置结点，和前一个结点，
    //     将前一个结点的指针指向要插入的结点，再将插入节点的指针指向指定位置的结点。
    public void add(int pos,T t){
        //获取需要插入节点
        Node node = new Node(t,null);
        //根据pos获取插入点的结点
        Node current = this.getNode(pos);
        //获取pos前面位置的结点
        Node before = this.getNode(pos - 1);
 
        //将before的next节点指向需要插入的结点
        before.next = node;
        //将插入节点的next指向当前pos上的结点
        node.next = current;
        //将链表中结点的数量加1
        this.size++;
    }

7.删除指定位置的元素

    //删除指定位置的元素
    //思路：获取到需要删除结点的位置，将前一个结点指针指向目标节点的指针。
    public T remove(int pos){
        //获取当前位置的前面一个节点
        Node before = this.getNode(pos - 1);
        //获取当前位置的结点
        Node current = this.getNode(pos);
        //当前位置前面的结点的next指向当前位置结点的next，(即当前位置下一个结点)
        before.next = current.next;
        //将将链表中结点的数量减1
        this.size--;
        return current.item;
    }

四、反转链表

1.用反转头实现 

思路：先创建一个反转头结点，然后将正序链表中的结点从前到后依次放入反转链表中，
//     同时，每次将结点放入反转链表都是插入到第一个结点，与反转头节点直接相连，
//     这里用循环逐个插入，最后将现有的头结点指向反转后的第一个结点即可。

    //链表的反转
    //思路：先创建一个反转头结点，然后将正序链表中的结点从前到后依次放入反转链表中，
    //     同时，每次将结点放入反转链表都是插入到第一个结点，与反转头节点直接相连，
    //     这里用循环逐个插入，最后将现有的头结点指向反转后的第一个结点即可。
    public void reverse(){
        //创建一个反转的头结点
        Node reverseHeader = new Node(null,null);
        //获取正序链表的第一个结点
        Node first = this.head.next;
        //循环执行
        while(first != null){
            //将原有的头结点指向first的next结点
            this.head.next = first.next;
            //将反转的next赋值给first的next
            first.next = reverseHeader.next;
            //将reverseHeader指向first
            reverseHeader.next = first;
            //从正序链表中获取第一个元素
            first = this.head.next;
        }
        //将现有头结点的next指向反转头节点的next，也就是指向反转后的首元结点
        this.head.next = reverseHeader.next;
    }

2.用递归实现反转链表

思路：递归反转就是从原链表的第一个存储节点开始，依次递归调用反转每一个结点，
//     直到把最后一个反转完毕，真个链表就反转完毕了。

//2.用递归实现反转链表
    //思路：递归反转就是从原链表的第一个存储节点开始，依次递归调用反转每一个结点，
    //     直到把最后一个反转完毕，真个链表就反转完毕了。
    public Node reverse2(Node curr){
        //判断是否存在下一个结点
        if(curr.next != null){
            //通过反转下一个结点，获取prev
            Node prev = reverse2(curr.next);
            //将之前的结点的next结点设置成当前结点
            prev.next = curr;
            //返回curr结点
        }else{
            //当前结点没有下一个结点
            //将头部结点的next指向当前结点
            this.head.next = curr;
        }
        return curr;
    }
 
    //调用reverse2
    public void getReverse2(){
        reverse2(this.head.next);
    }

五、用快慢指针获取链表中的值

1.快慢指针获取链表中间的值

思路：定义两个指针，一个快指针，一个慢指针，
//     快指针每次移动两个节点，慢指针每次移动一个节点
//     当快指针移动到链表尾部时，慢指针刚好移动到链表中间

  

//1.通过快慢指针获取中间的元素的值
    //思路：定义两个指针，一个快指针，一个慢指针，
    //     快指针每次移动两个节点，慢指针每次移动一个节点
    //     当快指针移动到链表尾部时，慢指针刚好移动到链表中间，将结点值返回即可
    public T getRKItem1(){
        //定义一个快指针
        Node fast = this.head.next;
        //定义一个慢指针
        Node slow = this.head.next;
        //同时移动快慢指针，快指针每次走2个节点，直到快指针到达链表尾部
        while(fast != null && fast.next != null){
            //移动慢指针
            slow = slow.next;
            //移动快指针
            fast = fast.next;
            fast = fast.next;
        }
        return slow.item;
    }

2.通过快慢指针获取倒数第k个结点值

思路：定义两个指针，一个快指针，一个慢指针，
//     快指针先移动到k-1的位置，慢指针每次移动一个节点
//     当快指针移动到链表尾部时，慢指针刚好移动到链表中间，将结点值返回即可

 //2.通过快慢指针获取倒数K位置的值
    //思路：定义两个指针，一个快指针，一个慢指针，
    //     快指针先移动到k-1的位置，慢指针每次移动一个节点
    //     当快指针移动到链表尾部时，慢指针刚好移动到链表中间，将结点值返回即可
    public T getRKItem2(int k){
        //定义一个快指针
        Node fast = this.head.next;
        //定义一个慢指针
        Node slow = this.head.next;
        //先将快指针移动到k-1的位置
        for(int i = 0;i1;i++){
            fast = fast.next;
        }
        //同时移动快慢指针，直到快指针移动到链表的尾部
        while(fast.next != null){
            //移动快指针
            fast = fast.next;
            //移动慢指针
            slow = slow.next;
        }
        return slow.item;
    }

六、循环链表

1.通过快慢指针判断链表是否有环

思路：定义两个指针，一个快指针，一个慢指针，
//     快指针每次移动两个节点，慢指针每次移动一个节点
//     如果链表有环，快指针和慢指针会在某次移动时相遇，表示有环。
//     相遇则返回true，不相遇则返回false 

//通过快慢指针判断链表是否有环
    //思路：定义两个指针，一个快指针，一个慢指针，
    //     快指针每次移动两个节点，慢指针每次移动一个节点
    //     如果链表有环，快指针和慢指针会在某次移动时相遇，表示有环。
    //     相遇则返回true，不相遇则返回false
    public boolean hasCircle(){
        //定义一个快指针
        Node fast = this.head.next;
        //定义一个慢指针
        Node slow = this.head.next;
        while (fast != null && fast.next != null){
            //移动快指针
            fast = fast.next.next;
            //移动慢指针
            slow = slow.next;
            //判断快指针和慢指针是否重合，从而判断出是否有环
            if (fast != null && fast.equals(slow)){
                return true;
            }
        }
        return false;
    }

2.通过快慢指针以及第三个指针获取环的入口元素

思路：先定义两个指针，一个快指针，一个慢指针，判断是否有环的循环里定义entry指针
//     快指针每次移动两个节点，慢指针每次移动一个节点
//     如果链表有环，快指针和慢指针会在某次移动时相遇，表示有环，
//     然后在判断中创建entry指针，entry指针和slow指针从头往后开始遍历，直到相遇即为入口。
//     相遇则返回true，不相遇则返回false

 //通过快慢指针判断链表是否有环
    //思路：先定义两个指针，一个快指针，一个慢指针，判断是否有环的循环里定义entry指针
    //     快指针每次移动两个节点，慢指针每次移动一个节点
    //     如果链表有环，快指针和慢指针会在某次移动时相遇，表示有环，
    //     然后在判断中创建entry指针，entry指针和slow指针从头往后开始遍历，直到相遇即为入口。
    //     相遇则返回true，不相遇则返回false
    public T hasCircleEntry(){
        //定义一个快指针
        Node fast = this.head.next;
        //定义一个慢指针
        Node slow = this.head.next;
        while (fast != null && fast.next != null){
            //移动快指针
            fast = fast.next.next;
            //移动慢指针
            slow = slow.next;
            //判断快指针和慢指针是否重合，从而判断出是否有环
            if (fast != null && fast.equals(slow)){
                //定义entry指针
                Node entry = this.head.next;
                while (!entry.equals(slow)){
                    //entry指针向后移动
                    entry = entry.next;
                    //慢指针向后移动
                    slow = slow.next;
                }
                //环的入口元素
                return entry.item;
            }
        }
        return null;
    }

七、约瑟夫问题

思路：先将元素添加到链表中，然后建成环装链表，
//     定义一个游标target，依次往后移动，如果遇到要移除的元素，
//     就将此结点的前一个结点的指针指向元素下一个结点，
//     定义一个count用来计数，按指定的间隔数计数，每移除一个元素count返回到初始值。

 

 

//解决约瑟夫问题，通过环形链表解决问题
    //思路：先将元素添加到链表中，然后建成环装链表，
    //     定义一个游标target，依次往后移动，如果遇到要移除的元素，
    //     就将此结点的前一个结点的指针指向元素下一个结点，
    //     定义一个count用来计数，按指定的间隔数计数，每移除一个元素count返回到初始值。
 
    //m是圈的总数
    //n是每次移除元素间隔的数量
    public void jsfKill(int m,int n){
        //构造一个循环链表
        for (int i = 1;i<=m;i++){
            this.add((T)(i+""));
        }
        //找到最后一个元素
        Node last = this.getNode(this.size - 1 );
        //建立环
        last.next = this.head.next;
 
        //
        //解决约瑟夫问题
        //定义一个游标
        Node target = this.head.next;
        //定义一个计时器
        int count = 1;
 
        //判断条件：当target == target.next时，即最后一个节点指针指向自己
        while(target != target.next){
            //将前一个元素的地址进行保存
            Node prev = target;
            //游标向后移动
            target = target.next;
            //计数
            /**
             * 这里自增自减有个知识点：
             * 1.如果一条语句中只有自增自减操作（如count++;），不管是++count还是count++，count的值都加一了
             * 2.如果一条语句中有其他变量（如int b = count++），那赋值遵循一个原则，即：
             * ++count：先自增后引用（count先加一，再赋值给b），count++：先引用后自增（count先赋值给b，再加一）
             */
            count++;
 
            //判断当前元素是否需要被移除
            if (count == n){
                System.out.println("移除的元素是："+target.item);
                //将前面元素的next指向target的next
                prev.next = target.next;
                //将target也指向next的元素
                target = target.next;
                //重新开始计数
                count = 1;
            }
        }
        System.out.println("最后剩下元素是："+target.item);
    }