数据结构与算法（第三章）

一、 什么是链表？

链表是一种存储数据集合的数据结构。有以下特性：

1， 相邻元素之间通过指针连接。

2， 最后一个元素的后继指针为NULL。

3， 程序执行中，链表长度可变。

4， 链表的空间可以按需分配

5， 没有内存空间的浪费，只是指针需要额外的内存开销。

二、 什么是数组？

也是存储数据的一种数据结构。

特点：

1， 在常数时间内访问数组之内的元素。这个过程呢就是，为了访问一个数组元素，需要计算其距离数组基地址的偏移量，用一个乘法计算偏移量，加上基地址的值，就是该元素的内存地址。

2， 数组占据的是一个连续的内存块。

3， 数组大小是固定的。

4， 数组插入一个元素操作负责，需要移动该位置后面的所有元素。

三、链表和数组比较

数组随机访问时间为常数级，链表为O(n)级。

链表插入和删除元素比数组更加快捷方便。

链表比数组占用更多的内存空间。

链表大小动态可变，数组固定大小。

四、链表具体介绍

单向链表

我们通常所说的都是单向链表，包含多个结点，每个结点都有指向下一个结点的next指针，链表最后一个结点next指针值为空，表示链表结束。

链表的基本操作：

遍历、链表中插入一个元素、链表中删除一个元素

单向链表插入分三种情况：

链表的表头插入一个结点、链表的中间插入一个结点、链表的末尾插入一个结点。

同样的删除也对应三种情况:

链表的表头删除一个结点、链表的中间删除一个结点、链表的末尾删除一个结点

下面是单向链表的具体示例：

首先是结点的数据结构，包含int类型的数据和ListNode类型的next指针，构造函数以及get/set方法。

public class ListNode {
    private int data;
    private ListNode next;

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

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}

接下来是针对单向链表的一些具体操作，包括循环打印结点的值，计算链表的长度、插入以及删除某个结点。

public class ListTest {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        listNode.setNext(listNode1);
        listNode1.setNext(listNode2);
        listNode2.setNext(listNode3);
        System.out.println(getLength(listNode));
        insertNode(listNode,2,new ListNode(5));
        printList(listNode);
        deleteNode(listNode,2);
        printList(listNode);
    }
    //print list node
    public static void printList(ListNode headNode){
        ListNode listNode = headNode;
        while(listNode != null){
            System.out.println(listNode.getData());
            listNode = listNode.getNext();
        }
    }

    //calculate list length
    public static int getLength(ListNode headNode) {
        int i = 0;
        ListNode currentNode = headNode;
        while (currentNode != null) {
            currentNode = currentNode.getNext();
            i++;
        }
        return i;
    }

    //insert list node
    public static ListNode insertNode(ListNode headNode,int position,ListNode listNode){
        if(headNode ==null){
            return listNode;
        }
        if( position < 1 || position > getLength(headNode) + 1) {
            System.out.println("position invalid");
        }else if(position == 1){
            listNode.setNext(headNode.getNext());
            headNode = listNode;
        }else{
            //include insert in the middle or in the last of the list
            int i = 1;
            ListNode tempNode = headNode;
            while(i < position - 1){
                tempNode = tempNode.getNext();
                i++;
            }
            listNode.setNext(tempNode.getNext());
            tempNode.setNext(listNode);
        }
        return headNode;
    }

    //delete list node
    public static ListNode deleteNode(ListNode headNode,int position){
        if(headNode == null){
            System.out.println("list is empty");
        }
        if( position < 1 || position > getLength(headNode) + 1) {
            System.out.println("position invalid");
            return headNode;
        }else if(position == 1){
            headNode = headNode.getNext();
        }else{
            int i = 1;
            ListNode tempNode = headNode;
            while(i < position -1){
                tempNode = tempNode.getNext();
                i++;
            }
            tempNode.setNext(tempNode.getNext().getNext());
        }
        return headNode;
    }
}

双向链表

在一个双向链表中，一个结点既知道自己的后继结点，也知道自己的前驱结点。

双向链表的缺点：

比单向链表更加占用内存空间，因为需要多一个指针指向前驱结点。

结点的插入、删除更加费时。

双向链表插入分三种情况：

链表的表头插入一个结点、链表的中间插入一个结点、链表的末尾插入一个结点

同样的删除也对应三种情况：

链表的表头删除一个结点、链表的中间删除一个结点、链表的末尾删除一个结点

下面是双向链表的具体示例：

首先是结点的数据结构，包含int类型的数据和ListNode类型的next指针，ListNode类型的pre指针，构造函数以及get/set方法。

public class DoubleListNode {
    private int data;
    private DoubleListNode next;
    private DoubleListNode pre;

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

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public DoubleListNode getNext() {
        return next;
    }

    public void setNext(DoubleListNode next) {
        this.next = next;
    }

    public DoubleListNode getPre() {
        return pre;
    }

    public void setPre(DoubleListNode pre) {
        this.pre = pre;
    }
}

接下来是针对双向链表的一些具体操作，包括循环打印结点的值，计算链表的长度、插入以及删除某个结点。

public class DoubleListTest {

    public static void main(String[] args) {

        DoubleListNode listNode = new DoubleListNode(1);
        DoubleListNode listNode1 = new DoubleListNode(2);
        DoubleListNode listNode2 = new DoubleListNode(3);
        DoubleListNode listNode3 = new DoubleListNode(4);
        listNode.setNext(listNode1);
        listNode1.setPre(listNode);
        listNode1.setNext(listNode2);
        listNode2.setPre(listNode1);
        listNode2.setNext(listNode3);
        listNode3.setPre(listNode2);
        System.out.println(getLength(listNode));
        insertNode(listNode,3,new DoubleListNode(9));
        printDoubleList(listNode);
        deleteNode(listNode,3);
        printDoubleList(listNode);
    }
    
    //print list node data
    public static void printDoubleList(DoubleListNode headNode){
        DoubleListNode listNode = headNode;
        while(listNode != null){
            System.out.println(listNode.getData());
            listNode = listNode.getNext();
        }
    }

    //calculate list length
    public static int getLength(DoubleListNode headNode) {
        int i = 0;
        DoubleListNode currentNode = headNode;
        while (currentNode != null) {
            currentNode = currentNode.getNext();
            i++;
        }
        return i;
    }

    //insert list node
    public static DoubleListNode insertNode(DoubleListNode headNode, int position, DoubleListNode listNode) {
        if (headNode == null) {
            return listNode;
        }
        if (position < 1 || position > getLength(headNode) + 1) {
            System.out.println("position invalid");
        } else if (position == 1) {
            listNode.setNext(headNode);
            headNode.setPre(listNode);
            return listNode;
        } else {
            int i = 1;
            DoubleListNode tempNode = headNode;
            while (i < position - 1) {
                tempNode = tempNode.getNext();
                i++;
            }
            listNode.setNext(tempNode.getNext());
            // if insert in the last of the list, avoid to case nullpointer
            if (tempNode.getNext() != null) {
                tempNode.getNext().setPre(listNode);
            }
            listNode.setPre(tempNode);
            tempNode.setNext(listNode);
        }
        return headNode;
    }

    //delete list node
    public static DoubleListNode deleteNode(DoubleListNode headNode, int position) {
        if (headNode == null) {
            return headNode;
        }
        if (position < 1 || position > getLength(headNode) + 1) {
            System.out.println("invalid position");
        } else if (position == 1) {
            DoubleListNode listNode = headNode.getNext();
            headNode = null;
            return listNode;
        } else {
            int i = 1;
            DoubleListNode tempNode = headNode;
            while (i < position - 1) {
                tempNode = tempNode.getNext();
                i++;
            }
            DoubleListNode pNode = tempNode.getNext();
            // if delete in the last of the list, avoid to case nullpointer
            if (pNode.getNext() != null) {
                tempNode.setNext(pNode.getNext());
            }
            pNode.getNext().setPre(tempNode);
            pNode = null;
        }
        return headNode;
    }
}

循环链表

和单向链表、双向链表都以null结尾不同，循环链表没有结束标志。轮询算法可以用循环链表来实现。

下面举两个循环链表的基本操作，遍历和计算长度。循环链表的结点和单向链表结点数据结构一致。这里不再给出。

public class CircleLIstTest {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode3 = new ListNode(4);
        listNode.setNext(listNode1);
        listNode1.setNext(listNode2);
        listNode2.setNext(listNode3);
        listNode3.setNext(listNode);
        System.out.println(getCircleListLength(listNode));
        printCircleListLength(listNode);
    }
    
    // calculate list length    
    public static int getCircleListLength(ListNode headNode){
        ListNode listNode = headNode;
        int length = 0;
        while(listNode != null){
            listNode = listNode.getNext();
            length++;
            if(listNode == headNode){
                break;
            }
        }
        return length;
    }
    //print list node data
    public static void printCircleListLength(ListNode headNode){
        ListNode listNode = headNode;
        while(listNode != null){
            System.out.println(listNode.getData());
            listNode = listNode.getNext();
            if(listNode == headNode){
                break;
            }
        }
    }
}

前面已经介绍了单向链表、双向链表、循环链表以及他们的一些基本操作。下面是给出针对链表的一些问题，其中一些巧妙地思路值得学习。

问题1：找到单向链表中的倒数第n个结点。

这个问题我们可能首先想到的就是先遍历整个链表得到链表的长度（假设为m），然后在重新遍历找到第m-n+1个就是倒数第n个结点。这里的时间复杂度是O(2m-n+1)。

那么是否有更加快捷的方法呢？答案是有的。

我们可以使用散列表，也就是哈希表。哈希表可以想象成一个java中的map。我们用结点的顺序值作为key，结点作为value。那么只需要遍历一次链表，生成哈希表。然后立马就可以根据key值m-n+1，得到这个结点。这个方法时间复杂度是O（m+1）。空间复杂度为O（m）。

除了第二个方法，是否有只扫描一次链表就解决问题的方法？

这里我们采用两个指针，开始都指向链表头结点。然后让其中一个指针先走n步，然后两个指针一起往下走，当一个指针到达末尾，另外一个正好处于倒数第n个节点处。时间复杂度为O(2m-n+1)。下面是使用两个指针时的代码。

ListNode getNNode(ListNode headNode, int n) {
        ListNode listNode = headNode;
        ListNode tempNode = null;
        for (int i = 1; i < n; i++) {
            if (listNode != null) {
                listNode = listNode.getNext();
            }
        }
        while (listNode != null) {
            if (tempNode == null) {
                tempNode = headNode;
            }else{
                tempNode = tempNode.getNext();
            }
            listNode = listNode.getNext();
        }
        if(tempNode != null){
            return tempNode;
        }
        return null;
    }

问题二：假设两个单链表在某个结点相交后，成为一个单向链表，两个链表的表头结点是已知的，相交的结点未知，相交之前各自的结点数是未知的，可能相同也可能不同。设计算法找到两个链表的合并点。

这里给出一种方法。

先分别遍历两个链表获得其长度（假设m,n且m>n），然后求出两个的差值（m-n），从较长的一个链表先走（m-n）步，然后两个链表同时遍历，直到出现两个后继指针相等的情况。则该结点就是相交结点。

public ListNode getIntersectNode(ListNode list1,ListNode list2){
        int i=0,j=0,sub;
        ListNode temp1 = list1;
        ListNode temp2 = list2;
        while(temp1 != null){
            i++;
            temp1 = temp1.getNext();
        }
        while(temp2 != null){
            j++;
            temp2 = temp2.getNext();
        }
        if(i < j){
            temp1 = list2;
            temp2 = list1;
            sub = j - i;
        }else{
            temp1 = list1;
            temp2 = list2;
            sub = i - j;
        }
        for(int k=0;k<sub;k++){
            temp1 = temp1.getNext();
        }
        while(temp1 != null && temp2 != null){
            if(temp1 == temp2){
                return temp1;
            }
            temp1 = temp1.getNext();
            temp2 = temp2.getNext();
        }
        return null;
    }

问题三：约瑟夫环，N个人想选出一个领头人，他们排成一个环，沿着环每数到第M个人，就从环中排除该人，并从下一个人重新计数，找出最后留在环中的人。

这里我们就可以用循环链表来解决这个问题，假设输入时一个有N个结点的循环链表，每个结点依次有一个编号（1-N）。代码如下：

public static ListNode getPosition(int N, int M){
        ListNode p = new ListNode(1);
        ListNode q;
        q = p;
        for(int i=2;i<=N;i++){
            ListNode r = new ListNode(i);
            p.setNext(r);
            p = r;
        }
        p.setNext(q);
        for(int j=N;j>1;j--){
            for(int k=0;k<M - 1;k++){
                p = p.getNext();
            }
            p.setNext(p.getNext().getNext());
        }
        System.out.println("the result is:" + p.getData());
        return p;
    }