线性表之链表(Linked List)

xiaohai 2021-06-21 21:01:07 2039人围观 标签: 算法 
简介链表是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能只管表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序而实现的,链表由一系列的节点(链表中的每一个元素称为结点)组成,节点可以在运行时动态生成。

链表是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能只管表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序而实现的,链表由一系列的节点(链表中的每一个元素称为结点)组成,节点可以在运行时动态生成。

链表是解决顺序表中插入和删除元素出现大量数据移动情况。

4.3.1、结点API设计和实现

API设计

类名 Node
构造方法 Node(T t,Node next):创建对象
成员变量 T item:存储数据
Node next:指向下一个结点

结点类实现

public class Node<T>{
    public T item;
    public Node next;

    public Node(T item,Node next){
        this.item = item;
        this.next = next;
    }
}

结点使用

public static void main(String[] args){

    //生成结点
    Node<Integer> one = new Node(1,null);
    Node<Integer> two = new Node(2,null);
    Node<Integer> three = new Node(3,null);
    Node<Integer> four = new Node(4,null);
    Node<Integer> five = new Node(5,null);

    //生成链表
    one.next = two;
    tow.next = three;
    three.next = four;
    four.next = five;

}

4.3.2、单向链表

4.3.2.1、定义

单向链表是链表的一种,它由多个结点组成,每个结点都是一个数据域和一个指针域组成,数据域来存储数据,指针域用来指向下一个节点。链表的头结点的数据域不存储数据,指针域指向第一个真正存储数据的节点。

图片alt

4.3.2.2、API设计和实现

API设计

类名 LinkList
构造方法 LinkList():创建LinkList()对象
成员内部类 private class Node 结点类
成员变量 private Node head:记录首结点
private int N:记录链表的长度
成员方法 public void clear():清空线性表
public boolean isEmpty():判断线性表是否为空,是返回true,否返回false
public int length():返回线性表的个数
public T get(int i):获取指定下标的元素
public void insert(int i,T t):指定位置插入元素
public void insert(T t):插入到线性表的最后
public T remove(int t):删除并返回线性表的第i个元素
public int indexOf(T t):返回线性表中首次出现指定数据元素的位置序号,若不存在,返回-1

实现类

package cn.test.algorithm.datastruct;

import java.util.Iterator;

public class LinkList<T> implements Iterable<T> {

    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class LIterator implements Iterator {

        private Node n;

        public LIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }

    //内部类
    private class Node {
        T item;//存储数据
        Node next;//下一个结点

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    private Node head;//记录头结点
    private int N;//记录链表的长度

    //构造方法
    public LinkList() {
        //初始化头结点
        this.head = new Node(null, null);

        //初始化元素个数
        this.N = 0;
    }

    //清空链表
    public void clear() {
        //将头结点的指向设置为null
        this.head.next = null;
        //设置元素的个数为0
        this.N = 0;
    }

    //获取链表长度
    public int length() {
        return N;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //获取指定位置的元素
    public T get(int i) {
        //通过循环从头结点开始往后找
        Node node = this.head;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return node.item;
    }

    //插入
    public void insert(T t) {
        Node node = this.head;
        //找到当前链表的最后一个结点
        for (int index = 0; index < N; index++) {
            node = node.next;
        }
        //创建新结点,保存元素
        Node newNode = new Node(t, null);

        //让当前链表最后一个结点指向新结点
        node.next = newNode;

        //元素个数+1
        N++;
    }

    //指定位置插入
    public void insert(T t, int i) {
        Node node = this.head;
        //找到i位置前一个结点
        for (int index = 0; index < i - 1; index++) {
            node = node.next;
        }
        //找到i位置的节点
        Node nodeI = node.next;
        //创建一个新结点,并且需要指向原来i位置的节点
        Node newNode = new Node(t, nodeI);
        //原来i位置的前一个节点指向新结点即可
        node.next = newNode;
        //元素+1
        N++;
    }

    //删除指定元素的位置
    public T remove(int i) {
        Node node = this.head;
        //找到i位置的前一个节点
        for (int index = 0; index < i - 1; index++) {
            node = node.next;
        }
        //找到i位置的节点
        Node nodeI = node.next;
        //把i位置的下一个结点指向i位置的前一个节点
        node.next = nodeI.next;
        //元素-1
        N--;
        return nodeI.item;
    }

    //根据结点值获取第一次出现的位置
    public int indexOf(T item) {
        Node node = this.head;
        int i = 1;
        while (true) {
            if (node == null || node.item.equals(item)) {
                break;
            }
            node = node.next;
            i++;
        }
        return i;
    }

    @Override
    public String toString() {
        return "LinkList{" +
                "head=" + head +
                ", N=" + N +
                '}';
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.LinkList;

public class TestLinkList {
    public static void main(String[] args) {
        LinkList<Integer> link = new LinkList<>();
        link.insert(1);
        link.insert(2);
        link.insert(3);
        link.insert(4);
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }

        link.insert(5, 1);
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }

        //删除第二个位置的元素
        link.remove(2);
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }

        //清空
        link.clear();
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }
    }
}

运行结果

LinkList{head=cn.test.algorithm.datastruct.LinkList$Node@4554617c, N=4}
遍历值:1
遍历值:2
遍历值:3
遍历值:4
LinkList{head=cn.test.algorithm.datastruct.LinkList$Node@4554617c, N=5}
遍历值:5
遍历值:1
遍历值:2
遍历值:3
遍历值:4
LinkList{head=cn.test.algorithm.datastruct.LinkList$Node@4554617c, N=4}
遍历值:5
遍历值:2
遍历值:3
遍历值:4
LinkList{head=cn.test.algorithm.datastruct.LinkList$Node@4554617c, N=0}

4.3.3、双向链表

4.3.3.1、定义

双向链表也叫双向表,是链表的一种,它由多个结点组成,每个结点都由一个数据域和两个指针域组成,数据域用来存放数据,其中一个指针域指向后继结点,另一个指针用来指向前驱结点。链表的头结点的数据域不存储数据,指向前驱结点的指针值为null,指向后续结点的指针域指向第一个真正的存储数据的节点。

图片alt

4.3.3.2、双向链表结点API设计和实现

API设计

类名 Node
构造方法 Node(T t,Node next):创建对象
成员变量 T item:存储数据
Node next:指向下一个结点
Node pre:指向上一个结点

结点实现类

public class Node<T>{
    public T item;
    public Node pre;
    public Node next;

    public Node(T item,Node pre,Node next){
        this.item = item;
        this.pre = pre;
        this.next = next;
    }
}

4.3.3.3、双向链表API设计和实现

类名 TwoWayLinkList
构造方法 TwoWayLinkList():创建TwoWayLinkList()对象
成员内部类 private class Node 结点类
成员变量 private Node first:记录首结点
private Node last:记录尾结点
private int N:记录链表的长度
成员方法 public void clear():清空线性表
public boolean isEmpty():判断线性表是否为空,是返回true,否返回false
public int length():返回线性表的个数
public T get(int i):获取指定下标的元素
public void insert(int i,T t):指定位置插入元素
public void insert(T t):插入到线性表的最后
public T remove(int t):删除并返回线性表的第i个元素
public int indexOf(T t):返回线性表中首次出现指定数据元素的位置序号,若不存在,返回-1
public T getFirst():获取第一个元素
public T getLast():获取尾元素

实现类

package cn.test.algorithm.datastruct;

import java.util.Iterator;

public class TwoWayLinkList<T> implements Iterable<T> {

    private Node first;//首结点
    private Node last;//尾节点

    private int N;//长度

    @Override
    public Iterator<T> iterator() {
        return new TIterator();
    }

    private class TIterator implements Iterator {

        private Node n;

        public TIterator() {
            this.n = first;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }

    //内部结点类
    private class Node {
        public T item;
        public Node pre;
        public Node next;

        public Node(T item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    //构造方法
    public TwoWayLinkList() {
        //初始化首节点和尾节点
        this.first = new Node(null, null, null);
        this.last = null;
        //初始化元素个数
        this.N = 0;
    }

    //清理
    public void clear() {
        //首节点回到初始化
        this.first.pre = null;
        this.first.next = null;
        this.first.item = null;
        //尾节点
        this.last = null;
        this.N = 0;
    }

    @Override
    public String toString() {
        return "TwoWayLinkList{" +
                "first=" + first +
                ", last=" + last +
                ", N=" + N +
                '}';
    }

    //获取长度
    public int length() {
        return this.N;
    }

    //是否为空
    public boolean isEmpty() {
        return this.N == 0;
    }

    //插入
    public void insert(T t) {
        //如果为空,说明首节点就是尾节点
        if (isEmpty()) {
            //生成新结点,前驱结点是first
            Node newNode = new Node(t, first, null);

            //新结点作为尾节点
            last = newNode;

            //首节点的后继结点指向last结点
            first.next = last;
        } else {
            //生成新结点,前驱结点是last
            Node newNode = new Node(t, last, null);

            //当前的last结点的后继结点指向新结点
            last.next = newNode;

            //新的尾节点为
            last = newNode;
        }

        //元素+1
        N += 1;

    }

    //指定位置插入
    public void insert(T t, int i) {
        //找到i位置的前一个节点
        Node pre = first;
        for (int index = 0; index < i - 1; index++) {
            pre = pre.next;
        }
        //找到i位子的节点
        Node currentNode = pre.next;

        //创建新结点
        Node newNode = new Node(t, pre, currentNode);

        //让i位置的前一个节点的的下一个结点变为新结点
        pre.next = newNode;
        //让i位置的前一个节点变为新结点
        currentNode.pre = newNode;

        //元素+1
        N++;
    }

    //获取第i个位置元素
    public T get(int i) {
        Node node = first.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return node.item;
    }

    //获取某个值第一次出现的位置
    public int indexOf(T t) {
        Node node = first;
        for (int index = 0; index < N; index++) {
            node = node.next;
            if (node.item.equals(t)) {
                return index;
            }
        }
        return -1;
    }

    //删除
    public T remove(int i) {
        //获取i位置的前一个结点
        Node pre = first;
        for (int index = 0; index < i - 1; index++) {
            pre = pre.next;
        }

        //找到i位置的节点
        Node currentNode = pre.next;

        //获取i位置的下一个节点
        Node nextNode = currentNode.next;

        //让i位置的前一个节点的下一个结点变为i位置的下一个结点
        pre.next = nextNode;

        //让i位置的后一个节点的前一个结点变为i位置的上一个结点
        nextNode.pre = pre;
        //个数-1
        N--;
        return currentNode.item;
    }


    //获取首结点的值
    public T getFirst() {
        if (!isEmpty()) {
            return first.next.item;
        }
        return null;
    }

    //获取尾节点的值
    public T getLast() {
        if (!isEmpty()) {
            return last.item;
        }
        return null;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.TwoWayLinkList;

public class TwoWayLinkListTest {
    public static void main(String[] args) {
        TwoWayLinkList<Integer> link = new TwoWayLinkList<>();
        System.out.println("---------------------正常插入-------------------------");
        link.insert(1);
        link.insert(2);
        link.insert(3);
        link.insert(4);
        System.out.println("首节点元素:"+link.getFirst());
        System.out.println("尾节点元素:"+link.getLast());
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }

        System.out.println("--------------------指定位置插入--------------------------");
        link.insert(5, 1);
        System.out.println("首节点元素:"+link.getFirst());
        System.out.println("尾节点元素:"+link.getLast());
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }
        System.out.println("---------------------获取操作-------------------------");
        System.out.println("获取第三个位置元素:"+link.get(3));
        System.out.println("获取值5的索引:"+link.indexOf(5));

        System.out.println("-------------------删除第二个元素---------------------------");
        //删除第二个位置的元素
        link.remove(2);
        System.out.println("首节点元素:"+link.getFirst());
        System.out.println("尾节点元素:"+link.getLast());
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }

        System.out.println("---------------------清空-------------------------");
        //清空
        link.clear();
        System.out.println("首节点元素:"+link.getFirst());
        System.out.println("尾节点元素:"+link.getLast());
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }


    }
}

运行结果

---------------------正常插入-------------------------
首节点元素:1
尾节点元素:4
TwoWayLinkList{first=cn.test.algorithm.datastruct.TwoWayLinkList$Node@4554617c, last=cn.test.algorithm.datastruct.TwoWayLinkList$Node@74a14482, N=4}
遍历值:1
遍历值:2
遍历值:3
遍历值:4
--------------------指定位置插入--------------------------
首节点元素:5
尾节点元素:4
TwoWayLinkList{first=cn.test.algorithm.datastruct.TwoWayLinkList$Node@4554617c, last=cn.test.algorithm.datastruct.TwoWayLinkList$Node@74a14482, N=5}
遍历值:5
遍历值:1
遍历值:2
遍历值:3
遍历值:4
---------------------获取操作-------------------------
获取第三个位置元素:3
获取值5的索引:0
-------------------删除第二个元素---------------------------
首节点元素:5
尾节点元素:4
TwoWayLinkList{first=cn.test.algorithm.datastruct.TwoWayLinkList$Node@4554617c, last=cn.test.algorithm.datastruct.TwoWayLinkList$Node@74a14482, N=4}
遍历值:5
遍历值:2
遍历值:3
遍历值:4
---------------------清空-------------------------
首节点元素:null
尾节点元素:null
TwoWayLinkList{first=cn.test.algorithm.datastruct.TwoWayLinkList$Node@4554617c, last=null, N=0}

4.3.4、Java中LinkedList实现

java中LinkedList集合也是使用的双向链表实现,并提供了增删改查的方法,下面我们根据源码查看是否满足如下要求:
①底层是否使用了双向链表

//插入
public boolean add(E e) {
    linkLast(e);
    return true;
}

//进入linkLast方法,从这里可以看出确实使用了双向链表
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

②结点类是否有三个域

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

存在三个域,E表示元素,next下一个结点,prev:前一个节点

4.3.5、链表时间复杂度分析

这里主要还是分析几个方法:

  • get(int i):获取元素值,每次查询都要从链表头开始进行查找,所以时间复杂度为O(n)
  • insert(T t,int t):插入指定位置元素,这里也是需要通过链表开头进行查找,所以随着元素的增多,查找的元素也比较多,时间复杂度为O(n)
  • remove(int i):每一次移除,需要先找到i元素的前一个元素,然后完成删除操作,随着元素N的增多,查找的元素越多,时间复杂度为O(n)

相比顺序表,链表插入和删除的时间复杂度虽然是一样的,但是任然有很大的有优势,因为链表的物理地址是不连续的,所以不需要预留指定的存储空间,不需要进行扩展,不需要进行元素交换。

相比顺序表,链表的查询效率性能会比较低,因此,我们的程序中查询操作较多,建议使用顺序表,增删操作比较多,建议使用链表。

4.3.6、链表的反转

如何对链表进行反转,需求如下:

  • 原链表:1->2->3->4
  • 反转后:4->3->2->1

使用递归可以完成反转,递归反转其实就是从原链表的第一个存储数据的节点开始,一次递归调用反转的每一个节点,直到把最后一个结点反转完毕,整个链表就反转完毕。

API设计

  • public void reverse():对整个链表反转
  • public Node reverse(Node cur):反转链表中的某个结点curr,把反转后的curr结点返回。
    图片alt

实现类

//在LinkList类中添加如下两个方法
//反转整个链表啊
public void reverse() {
    //判断当前链表是否为空
    if (isEmpty()) {
        return;
    }
    //不为空就进行结点反转调用
    reverse(head.next);
}

//反转单个结点
public Node reverse(Node curr) {
    //如果为空表示最后一个结点,需要首节点的next指向该结点
    if (curr.next == null) {
        head.next = curr;
        return curr;
    }
    //递归反转当前结点的下一个结点,返回值就是链表反转后当前结点的上一个结点
    Node pre = reverse(curr.next);
    //将返回的节点的下一个结点编程当前结点
    pre.next = curr;
    //需要将curr的下一个结点变成null
    curr.next = null;
    return curr;
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.LinkList;

public class TestLinkList {
    public static void main(String[] args) {
        LinkList<Integer> link = new LinkList<>();
        link.insert(1);
        link.insert(2);
        link.insert(3);
        link.insert(4);
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }

        System.out.println("---------------链表反转-----------------");
        link.reverse();
        System.out.println(link.toString());
        for (Integer integer : link) {
            System.out.println("遍历值:" + integer);
        }
    }
}

返回结果

LinkList{head=cn.test.algorithm.datastruct.LinkList$Node@4554617c, N=4}
遍历值:1
遍历值:2
遍历值:3
遍历值:4
---------------链表反转-----------------
LinkList{head=cn.test.algorithm.datastruct.LinkList$Node@4554617c, N=4}
遍历值:4
遍历值:3
遍历值:2
遍历值:1

4.3.7、快慢指针

快慢指针是定义两个指针,这两个指针移动的速度一快一慢,一次来制造出自己想要的差值,这个差值可以让我们找到链表上相应的节点。一般情况下快指针的移动步长是慢指针的两倍。

4.3.7.1、中间值问题

如下的测试类

package cn.test.algorithm.test;

public class SlowFastTest {
    public static void main(String[] args) {

        Node<String> node1 = new Node<>("node1", null);
        Node<String> node2 = new Node<>("node2", null);
        Node<String> node3 = new Node<>("node3", null);
        Node<String> node4 = new Node<>("node4", null);
        Node<String> node5 = new Node<>("node5", null);
        Node<String> node6 = new Node<>("node6", null);
        Node<String> node7 = new Node<>("node7", null);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;


        //查找中间值
        String mid = getMid(node1);

        System.out.println("中间值为:" + mid);
    }

    //获取中间值
    public static String getMid(Node<String> first) {
        return null;
    }

    //结点类
    private static class Node<T> {
        T item;//结点

        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

需求:请完成测试类Test中的getMid方法,可以找出链表的中间元素值并返回。

利用快慢指针,我们把链表可以看成一个跑到,假设a的速度是b的两倍,那么当a跑完全程后,b刚好跑了一半,以此来达到目的。

如下图,最开始,slow和fast指针都指向链表第一个结点,然后slow每次移动一个指针,fast每次移动两个指针。
图片alt

getMid的实现方式,如下:

public static String getMid(Node<String> first) {
    //定义两个指针,都指向第一个结点
    Node<String> fast = first;
    Node<String> slow = first;

    //需要遍历链表,当快指针指向的节点没有下一个结点就结束
    while (fast != null && fast.next != null) {

        fast = fast.next.next;

        slow = slow.next;
    }

    //只需要返回慢指针的节点就是中间值

    return slow.item;
}

运行结果:

中间值为:node4

4.3.7.2、单向链表是否有环问题

  • 无环链表:快慢指针不会相遇
  • 有环链表:快慢指针会相遇
    图片alt

根据下面代码,完成需求:

package cn.test.algorithm.test;

public class CircleTest {
    public static void main(String[] args) {

        Node<String> node1 = new Node<>("node1", null);
        Node<String> node2 = new Node<>("node2", null);
        Node<String> node3 = new Node<>("node3", null);
        Node<String> node4 = new Node<>("node4", null);
        Node<String> node5 = new Node<>("node5", null);
        Node<String> node6 = new Node<>("node6", null);
        Node<String> node7 = new Node<>("node7", null);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        //将node7结点指向node3
        node7.next = node3;


        //是否有环
        Boolean isCircle = isCircle(node1);

        System.out.println("链表是否有环:" + isCircle);
    }

    //判断链表是否有环
    public static Boolean isCircle(Node<String> first) {

        return false;
    }

    //结点类
    private static class Node<T> {
        T item;//结点

        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

需求:

请完善测试类CircleTest类中的isCircle方法,返回链表中是否有环。

使用快慢指针思想,还是把链表作为一个跑道,链表中又环,那么这条跑道就是一个圆环跑道,在一条圆环跑道中,两个人有速度差,那么迟早两人会相遇,相遇说明就是有环。

图片alt

图片alt

图片alt

方法实现:

public static Boolean isCircle(Node<String> first) {

    //定义快慢指针
    Node<String> fast = first;
    Node<String> slow = first;

    //遍历链表,如果快慢指针指向了同一个结点,那么证明有环
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            return true;
        }
    }
    return false;
}

运行结果:

链表是否有环:true

//屏蔽掉node7.next = node3;后运行
链表是否有环:false

4.3.7.3、有环链表入口问题

需求代码如下:

package cn.test.algorithm.test;

public class CircleEnterTest {
    public static void main(String[] args) {

        Node<String> node1 = new Node<>("node1", null);
        Node<String> node2 = new Node<>("node2", null);
        Node<String> node3 = new Node<>("node3", null);
        Node<String> node4 = new Node<>("node4", null);
        Node<String> node5 = new Node<>("node5", null);
        Node<String> node6 = new Node<>("node6", null);
        Node<String> node7 = new Node<>("node7", null);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        //将node7结点指向node3
        node7.next = node3;


        //是否有环
        Node<String> enter = circleEnter(node1);
        if (enter != null) {
            System.out.println("有环链表入口值:" + enter.item);
        } else {
            System.out.println("不是有环链表");
        }
    }

    //有环链表入口结点
    public static Node<String> circleEnter(Node<String> first) {

        return null;
    }

    //结点类
    private static class Node<T> {
        T item;//结点

        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

当快慢指针相遇时,可以判断链表是否有环,这时候重新定义一个新的指针指向链表的起点,且步长跟慢指针一样为1,则慢指针与新指针相遇的地方就是环的入口,这个证明过程需要设计数论的知识,所以这里就不说明,只展示实现。

图片alt
图片alt

方法实现:

//有环链表入口结点
public static Node<String> circleEnter(Node<String> first) {

    //定义快慢指针
    Node<String> fast = first;
    Node<String> slow = first;
    Node<String> tmp = null;

    //遍历找到是否是有环链表
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        //快慢指针相遇,临时指针指向首结点
        if (fast == slow && tmp == null) {
            tmp = first;
            continue;
        }

        //临时指针变换
        if (tmp != null) {
            tmp = tmp.next;

            //判断临时指针和慢指针相遇
            if (tmp.equals(slow)) {
                return tmp;
            }
        }
    }

    return null;
}

运行结果:

有环链表入口值:node3

4.3.8、循环链表

循环链表就是链表整体要形成一个圆环形,在单向链表中,我们最后一个结点指针是null,不指向任何结点,那么要实现循环链表,那么最后一个结点就要指向头结点。

图片alt

循环链表实现:

package cn.test.algorithm.datastruct;

//循环链表
public class CircleLinkList {
    public static void main(String[] args) {
        Node<String> node1 = new Node<>("node1", null);
        Node<String> node2 = new Node<>("node2", null);
        Node<String> node3 = new Node<>("node3", null);
        Node<String> node4 = new Node<>("node4", null);
        Node<String> node5 = new Node<>("node5", null);
        Node<String> node6 = new Node<>("node6", null);
        Node<String> node7 = new Node<>("node7", null);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;

        //将node7结点指向node3
        node7.next = node3;
    }

    //结点类
    private static class Node<T> {
        T item;//结点

        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

4.3.9、约瑟夫问题

问题描述:在罗马人占领乔塔特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

问题转换:

  • 41个人坐一圈,第一个人编号为1,第二个人编号为2,第n个人编号为n;
  • 编号为1的人开始从1报数,依次向后报数,报数为3的那个人退出;
  • 自退出的那个人开始的下一个人开始从1开始报数,依次类推;
  • 求出最后退出的那个人的编号;

图片alt

解题思路:

  • 构件含有41个节点的单向循环链表,分别存储1-41的值,分别代表着41个人;
  • 使用计数器count,记录当前报数的值
  • 遍历链表,每循环一次,count++
  • 判断count的值,如果是3,则从链表中删除这个节点并打印节点的值,把count的值重置为0

实现类:

package cn.test.algorithm.test;

public class JosephusTest {
    public static void main(String[] args) {
        //构件循环链表包含41个节点,分别存储1-41的值
        //首结点
        Node<Integer> first = null;
        //记录前一个结点
        Node<Integer> pre = null;
        for (int i = 1; i <= 41; i++) {
            Node<Integer> node = new Node<>(i, null);//初始化新结点

            if (i == 1) {//第一个结点
                first = node;
            } else {
                pre.next = node;
            }
            pre = node;

            //如果是最后一个结点
            if (i == 41) {
                pre.next = first;
            }

        }
        //打印
        Node<Integer> node = first;
        System.out.print("结点数据:【");
        for (int i = 0; i < 41; i++) {
            System.out.print(node.item + ",");
            node = node.next;
        }
        System.out.println("】");
        //计数器count,进行计数
        int count = 0;

        //遍历循环链表
        Node<Integer> n = first;//记录每次遍历的结点,默认从首结点开始
        Node<Integer> before = null;//记录当前结点的上一个结点
        System.out.print("删除结点:【");
        while (n != n.next) {
            //模拟报数
            count++;

            //判断当前报数是不是3
            if (count == 3) {
                //如果是3,把当前结点删除,打印当前结点,重置count=0,当前结点下一一位
                System.out.print(n.item + ",");
                before.next = n.next;
                count = 0;
            } else {
                //如果不是3,只需要让当前结点后移一位,当前结点的before变为当前结点
                before = n;
            }
            n = n.next;
        }
        System.out.println(n.item + "】");
    }

    //结点类
    private static class Node<T> {
        T item;//结点

        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

运行结果:

结点数据:【1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,】
删除结点:【3,6,9,12,15,18,21,24,27,30,33,36,39,1,5,10,14,19,23,28,32,37,41,7,13,20,26,34,40,8,17,29,38,11,25,2,22,4,35,16,31】