数据结构——链表

参考代码

单向链表

单向链表由各个内存通过 next 指针连接在一起组成。

文字解析：

• data数据+next指针，组成一个链表元素的内存结构
• 第一个元素称为表头head，最后一个元素称为表尾tail
• 表尾的next指针设置为null
• 单链表的遍历方向单一

单链表图示：

插入操作：

删除操作：

反转操作：

示例代码如下：

```
/**
 * 单向链表
 */
public class SinglyLinkedList {
    private Node nil = new Node(0); //辅助头节点nil
    private Node head; //头节点
    private int size = 0; //链表长度

    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 初始化单链表
     * 头插法
     * 顺序相反
     *
     * @param nums
     * @return
     */
    public boolean initWithHead(int[] nums) {
        if (nums == null || nums.length == 0)
            return false;
        for (int i = 0; i < nums.length; i++) {
            Node node = new Node(nums[i]);
            size++;
            node.next = nil.next;
            nil.next = node;
        }
        head = nil.next;
        return true;
    }

    /**
     * 初始化单链表
     * 尾差法
     *
     * @param nums
     * @return
     */
    public boolean initWithTail(int[] nums) {
        if (nums == null || nums.length == 0)
            return false;
        Node temp = nil;
        for (int i = 0; i < nums.length; i++) {
            Node node = new Node(nums[i]);
            size++;
            temp.next = node;
            temp = node;
        }
        head = nil.next;
        return true;
    }

    /**
     * 在指定位置插入元素
     *
     * @param data
     * @param index 从0开始计算
     * @return
     */
    public boolean insert(int data, int index) {
        if (index < 0 || index > size)
            return false;
        Node temp = nil;
        while (index-- > 0) {
            temp = temp.next;
        }
        Node node = new Node(data);
        node.next = temp.next;
        temp.next = node;
        size++;
        head = nil.next;
        return true;
    }

    /**
     * 删除指定位置的节点
     *
     * @param index 从0开始计算
     * @return
     */
    public boolean delete(int index) {
        if (index < 0 || index >= size)
            return false;
        Node temp = nil;
        while (index-- > 0) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
        size--;
        head = nil.next;
        return true;
    }

    /**
     * 反转单链表
     * 若链表nil->1->2->null
     * 1. prev=null,cur=1:null<-1
     * 2. prev=1,cur=2:null<-1<-2
     * null<-1<-2<-nil
     */
    public void reverse() {
        Node cur = head;
        Node prev = null;
        while (cur != null) {
            Node next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        nil.next = prev;
        head = nil.next;
    }

    /**
     * 从头到尾遍历单链表
     */
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        int[] nums = {1, 2, 3, 4, 5};
        list.initWithTail(nums);
        list.printList();
        System.out.println("链表的长度为：" + list.size);
        list.insert(6, 0);
        list.printList();
        System.out.println("链表的长度为：" + list.size);
        list.delete(5);
        list.printList();
        System.out.println("链表的长度为：" + list.size);
        list.reverse();
        list.printList();
    }
}
```

链表判断是否有环

使用两个slow, fast指针从头开始扫描链表。指针slow每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。

```
/**
     * 判断单链表是否有环路
     * 算法思想：
     * 设定两个快慢指针slow和fast
     * 其中slow每次向前一步，fast每次向前两步
     * 那么，如果链表存在环，则slow和fast相遇，相当于fast已经超越slow一圈
     * 若链表没有环，则fast最先到达链表末尾
     *
     * @param head
     * @return
     */
    public boolean hasCircle(Node head) {
        if (head == null)
            return false;
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast)
                return true;
        }
        return false;
    }
```

链表环的长度

在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2*len步，相遇时多走了一圈：环长=2*len-len。

```
/**
     * 环的长度
     *
     * @param head
     * @return
     */
    public int circleLen(Node head) {
        if (!hasCircle(head))
            return 0;
        Node slow = head;
        Node fast = head;
        Node pos = null;
        //一定有环
        while (true) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                pos = slow;
                break;
            }
        }
        int sLen = 0;
        int fLen = 0;
        slow = pos;
        fast = pos;
        while (true) {
            slow = slow.next;
            fast = fast.next.next;
            sLen += 1;
            fLen += 2;
            if (slow == fast) {
                break;
            }
        }
        return fLen - sLen;
    }
```

链表环连接点的位置

在环上相遇后，记录第一次相遇点为pos，连接点为intersection point，假设头结点到连接点的长度为len，连接点到第一次相遇点的长度为x，环长为R。

第一次相遇时，slow走的长度 S = len + x;

第一次相遇时，fast走的长度 2S = len + n*R + x;

所以可以知道，len + x = n*R;　　len = n*R - x;

```
/**
     * 求环连接点的位置
     *
     * @param head
     * @return
     */
    public Node intersectionPoint(Node head) {
        if (!hasCircle(head))
            return null;
        Node slow = head;
        Node fast = head;
        Node pos = null;
        //一定有环
        while (true) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                pos = slow;
                break;
            }
        }
        Node pHead = head;
        while (pHead != pos) {
            pHead = pHead.next;
            pos = pos.next;
        }
        return pHead;
    }
```

双向链表

双向链表：由各个内存结构通过指针 next 和指针 prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构【链头没有前驱，链尾没有后继】，内存结构由数据域、prev 指针域和 next 指针域组成。

文字解析：

• data 数据 + next 指针 + prev 指针，组成一个双向链表的内存结构；
• 第一个内存结构称为链头，最后一个内存结构称为链尾；
• 链头的 prev 指针设置为null， 链尾的 next 指针设置为null；
• prev 指向的内存结构称为前驱， next 指向的内存结构称为后继；
• 双向链表的遍历是双向的，即如果把从链头的 next 一直到链尾的遍历方向定义为正向，那么从链尾的 prev 一直到链头的遍历方向就是反向；

双链表图示：

示例代码如下：

```
public class DoublyLinkedList {
    private Node nil = new Node(0);
    private int size = 0;
    private Node head;

    public static class Node {
        int data;  //关键字
        Node prev; //头指针，指向前驱元素
        Node next; //尾指针，指向后继元素

        public Node(int data) {
            this.data = data;
        }
    }

    public DoublyLinkedList() {
        //初始化一个空的链表，由一个哨兵组成！
        nil.next = null;
        nil.prev = null;
    }

    /**
     * 从链表的头部插入
     *
     * @param data
     */
    public void insert(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            head.prev = nil;
            nil.next = head;
            size += 1;
        } else {
            node.next = nil.next;
            nil.next.prev = node;
            nil.next = node;
            node.prev = nil;
            size += 1;
            head = nil.next;
        }
    }

    /**
     * 从链表的头部删除
     */
    public void delete() {
        if (head == null)
            return;
        head.prev.next = head.next;
        head.next.prev = head.prev;
        size -= 1;
        head = nil.next;
    }

    /**
     * 从头到尾遍历链表
     */
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        DoublyLinkedList linkedList = new DoublyLinkedList();
        for (int i : nums) {
            linkedList.insert(i);
        }
        linkedList.printList();
        linkedList.delete();
        linkedList.printList();
    }
}
```

循环链表

单向循环链表：由各个内存结构通过一个指针 next 链接在一起组成，每一个内存结构都存在后继内存结构，内存结构由数据域和 next 指针域组成。

双向循环链表：由各个内存结构通过指针 next 和指针 prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由数据域、prev 指针域和 next 指针域组成。

文字解析：

• 循环链表分为单向、双向两种；
• 单向的实现就是在单链表的基础上，把链尾的 next 指针直接指向链头，形成一个闭环；
• 双向的实现就是在双向链表的基础上，把链尾的 next 指针指向链头，再把链头的 prev 指针指向链尾，形成一个闭环；
• 循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头和链尾；

单向循环链表图示：

双向循环链表图示：