认识单链表

一、ArrayList的优点及缺陷
二、链表
- 2.1 链表的概念及结构
- 2.2 链表的实现
三、链表面试题

一、ArrayList的优点及缺陷

优点：
适合给定下标位置进行查找元素。此时可以达到O(1)。
缺陷：

由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。
ArrayList是按照1.5倍大小来扩容的。假设现在有100个空间，而我们恰恰需要101个空间，这时候默认会扩容为150个空间，造成了空间的严重浪费。

因此：java集合中又引入了LinkedList，即链表结构。

二、链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

注意:

从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
现实中的结点一般都是从堆上申请出来的
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

虽然有这么多的链表的结构，但是我们重点掌握两种:

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.2 链表的实现

先用一个比较low的办法来实现MySingleList：

public class MySingleList {
    /**
     * 节点内部类
     */
    static class ListNode{
        public int val;
        public ListNode next;

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

    public ListNode head; // 不初始化了，默认就是null

    public void createList(){
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        this.head = listNode1;
    }
}

public class Test {
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.createList();
    }
}

一般情况下，链表并不是用以上方式构造，而是通过add方法构造的：

public class Test {
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addFirst(3);
        mySingleList.addFirst(2);
        mySingleList.addLast(4);
        mySingleList.addFirst(1);
        mySingleList.addLast(5);
        mySingleList.display();
    }
}

display方法：
三个细节：

拷贝一个head指针来移动；
while判断条件不能为cur -> next != null；
通过cur = cur.next来使cur走动。

addFirst方法：
比起顺序表的好处是：插入数据的时候不用挪动元素，只需要修改指向即可。
链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。

细节：

若是一个空链表，也没有任何问题：

技巧：当你在链表当中插入一个数据的时候，一定要记住先去绑定后面的节点。

addLast方法：
细节：

    public void addLast(int data){
		ListNode node = new ListNode(data);

        ListNode cur = this.head;
        while(cur.next != null){
            cur = cur.next;
        }
        // 到这里cur已经是尾巴节点了
        cur.next = node;
    }

以上代码，若本身就是一个空链表（head = null）呢？？？空指针异常！！！
所以我们需要先去判断是否为空，正确代码：

    public void addLast(int data){
        ListNode node = new ListNode(data);

        ListNode cur = this.head;
        if(cur == null){
            this.head = node;
        }else{
            while(cur.next != null){
                cur = cur.next;
            }
            // 到这里cur已经是尾巴节点了
            cur.next = node;
        }
    }

addIndex方法：

    public void addIndex(int index,int data){}

细节：

先判断index的合法性：
index < 0 || index > size()：不合法（抛异常）；
index == 0：头插；index == size()：尾插。
头插或者尾插情况完成后一定要return;！！！

注意：
方法内部需要的接口方法可以用private来封装，不会被类外看到。
（比如此方法里调用的 findIndexSubOne 方法）

remove方法：
细节：

对空链表、删除第一个节点情况特殊处理 （记得return！！！）
先找到 del(key) 的前一个节点
cur.next = cur.next.next;

注意：
下面找key前一个位置的代码有什么问题？

    private ListNode findPrevOfKey(int key){
        ListNode cur = this.head;
        while(cur.next.val != key){
            cur = cur.next;
        }
        return cur;
    }

答：若key不存在，上述代码运行时会发生空指针异常！所以，我们应该再加一层限制：

    private ListNode findPrevOfKey(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        // 没找到 return null;
        return null;
    }

removeAllKey方法：
有的同学可能会这样想：我们循环调用刚刚讲解的remove方法不就可以了？那么循环多少次呢？假设有n个节点，我们循环n次的话，整个时间复杂度就达到了O(n²)，并不是一个好方法！！！
首先，我们判断是否为空链表，若是直接return；
其次，我们可以定义前后两个指针：

而第一个节点需要单独判断：

若放在上述代码之后：
若放在上述代码之前：
需要把 if 改成 while：把第一个位置的key值节点全部删除完。

clear()方法：
当我们让 head = null 时，第二个节点就没有对象引用，被回收，以此类推。

代码实现：

public class MySingleList {
    /**
     * 节点内部类
     */
    static class ListNode{
        public int val;
        public ListNode next;

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

    public ListNode head; // 不初始化了，默认就是null


    public void display(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(key == cur.val){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    public void addLast(int data){
        ListNode node = new ListNode(data);

        ListNode cur = this.head;
        if(cur == null){
            this.head = node;
        }else{
            while(cur.next != null){
                cur = cur.next;
            }
            // 到这里cur已经是尾巴节点了
            cur.next = node;
        }
    }

    public void addIndex(int index,int data) throws IndexWrongfulException{
    	// 1.判断index合法性
        if(index < 0 || index > this.size()){
            throw new IndexWrongfulException("index位置不合法");
        }
        // 2.特殊位置插入
        if(index == 0){
            this.addFirst(data);
            return;
        }
        if(index == size()){
            this.addLast(data);
            return;
        }
        // 3.中间插
        // new
        ListNode node = new ListNode(data);
        // 先走 index-1 步，找到 cur
        ListNode cur = this.findIndexSubOne(index);
        // 修改指向
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode findIndexSubOne(int index){  // 不用判断index合法性，因为走到这儿index一定合法了
        ListNode cur = this.head;
        while((index-1) != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    public void remove(int key){
        // 空链表：
        if(this.head == null){
            return;
        }
        // 删除第一个节点：
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }

        ListNode cur = this.findPrevOfKey(key);
        if(cur == null){     // 可能就没有key数据！！！
            System.out.println("没有你要删除的数字！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
        // 或 cur.next = cur.next.next;
    }

    private ListNode findPrevOfKey(int key){
        ListNode cur = this.head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        // 没找到 return null;
        return null;
    }

    public void removeAllKey(int key){
        if(this.head == null){
            return;
        }
        ListNode prev = this.head;
        ListNode cur = this.head.next;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){
            head = head.next;
        }
    }

    public void clear(){
        this.head = null;
    }

}

public class IndexWrongfulException extends RuntimeException{
    public IndexWrongfulException() {
    }

    public IndexWrongfulException(String message) {
        super(message);
    }
}

public class Test {
    public static void main(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addFirst(3);
        mySingleList.addFirst(2);
        mySingleList.addLast(4);
        mySingleList.addFirst(1);
        mySingleList.addLast(5);
        try{
            mySingleList.addIndex(2,6);
        }catch (IndexWrongfulException e){
            e.printStackTrace();
        }
        mySingleList.remove(6);
        mySingleList.addFirst(5);
        mySingleList.removeAllKey(5);
        mySingleList.display();
        System.out.println(mySingleList.size());
        System.out.println("=====================================================");
        mySingleList.clear();
        mySingleList.display();
    }
}

三、链表面试题

3.1 反转单链表

OJ链接

思路：（头插法）

代码：

    // 反转链表
    public ListNode reverseList() {
        if(head == null){
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

3.2 返回中间节点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
OJ链接

思路：
我们可以先遍历一遍得到 size，然后第二遍再走 size/2 步即可。
但若要求只能遍历一遍呢？
这时我们可以使用快慢指针法：

代码：

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

注意：

        while(fast != null && fast.next != null){

这一行代码不能改变判断的先后顺序：
如果把 fast.next != null 放在前面，若 fast == null ，会发生空指针异常！！！

3.3 倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。
OJ链接

思路：
我们可以先遍历一遍得到 size，然后第二遍再走 size - k 步即可。
但若要求只能遍历一遍呢？
这时我们可以使用快慢指针法：

注意：

先判断k的合法性。
时刻注意避免空指针异常！！！

代码：

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

        public int size(ListNode head){
        int count = 0;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

}

=============================================================================
改进：
判断k的合法性时：

        if(k <= 0 || k > size(head)){

这样判断的话，size()方法会先遍历一遍链表，所以我们可以之后再判断上界：

        while((k-1) != 0){
            fast = fast.next;
            if(fast == null){
                return null;
            }
            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){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

3.4 合并链表

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

思路：

代码：

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

3.5 以x分割链表

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
OJ链接

思路：

两个链表都设置头尾两个指针。

注意：

时刻注意避免空指针异常！！！
最后ae.next要置空啊！：ae.next = null;

代码：

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead == null){
            return null;
        }
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = pHead;
        // 遍历链表，当 cur == null 时遍历完成
        while(cur != null){
            if(cur.val < x){
                if(bs == null){     // 第一次插入节点
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null){
                    as = cur;
                    ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        if(bs == null){       // 第一个段 没有数据
            return as;
        }else{
            be.next = as;
            // 手动置空！
            if(ae != null){
                ae.next = null;
            }
            return bs;
        }
    }
}

3.6 链表的回文结构

OJ链接

思路：将中间节点后的所有节点逆置，两边同时向中间走进行比较。

用快慢指针法找到中间节点 slow 。
用头插法进行后半段逆序：（下图是逆序后）

然后两边同时向中间走进行比较：

写完后提交代码，我们发现并不能通过，这是因为偶数个数节点情况下会出现问题！！！

各走两步后：

出现了错误！！！
所以，在判断回文的代码中，我们需要加入：

代码：

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        // null：不是回文
        if(A == null){
            return false;
        }
        // 一个节点：是回文
        if(A.next == null){
            return true;
        }

        // 找中间节点：
        ListNode slow = A;
        ListNode fast = A;
        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;
        }

        // 开始判断回文：
        ListNode head = A;
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            // 偶数个数节点时需要判断：
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

3.7 相交链表

输入两个链表，找出它们的第一个公共结点。
OJ链接

思路：
链表相交后的长度一定相等，所以长度差即为相交前的长度差。
代码：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 1.求链表的长度
        ListNode pl = headA;  // pl要永远指向最长的链表
        ListNode ps = headB;  // ps要永远指向最短的链表
        int lenA = 0;
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        int lenB = 0;
        while(ps != null){
            lenB++;
            ps = ps.next;
        }
        // pl和ps再指回去！
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        // 这时，pl永远指向了最长的链表；ps要永远指向最短的链表
        // 2.让最长的链表 先走len步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        // 3. pl和ps 现在在相同的起始位置，同时往后走
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        // 走到这里pl和ps相等了，即相交？
        // 但也可能都是null啊，这样的话不叫相交：(但此判断可有可无)
        if(pl == null){
            return null;
        }
        return pl;
    }
}

在编译器测试时，我们怎么构造出两个相交链表呢？很简单：
比如：headB.next.next = headA.next.next;

3.8 判断是否有环

给定一个链表，判断链表中是否有环。
OJ链接

思路：
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。
代码：

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

【扩展问题】：

为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步，走4步，…n步行吗？

在编译器测试时，我们怎么构造出环呢？很简单：

3.9 入环节点

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
OJ链接

结论：
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
证明：

代码：

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