public class MysingleList {
        static class ListNode{
            public int val;
            public ListNode next;

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

?接着再简单的建立一个ListNode

      public ListNode head;//默认就是null

        public void creatList() {
            ListNode listNode1 = new ListNode(12);
            ListNode listNode2 = new ListNode(23);
            ListNode listNode3 = new ListNode(34);
            ListNode listNode4 = new ListNode(45);
            ListNode listNode5 = new ListNode(56);

            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
            listNode4.next = listNode5;
            this.head = listNode1;//头结点
        }

head就是头结点

那么head如何从上一个节点走到下一个节点呢？

通过：? head?= head.next

遍历链表：

我们先看打印这个链表：

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

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

?两种方法不同的地方在于到底是head为空还是head.next为空的时候停下来呢？

当head.next为空再停下来，这是head并不会等于head.next,那么最后一个元素就不会打印到。

但是又有新的问题出现：这样做next就会访问到null去了，所以我们需要一个新的节点来代替next

更新过后的代码：

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

?2.判断是否包含某个数（contains）

查看这个链表是否包含某个数字：

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

3.头插法(addFirst)

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

比起顺序表的好处：插入数据的时候不需要挪动元素，只需要修改指向即可

4.尾插法（addLast）

        public void addLast(int data){
            ListNode cur = this.head;
            while(cur != null){
                cur = cur.next;
            }
            ListNode node = new ListNode(data);
        }

依照头插法的思想，我们很容易想到这样子表示尾插法。但如果整个链表为空，那么就会出现空指针异常的问题。

所以经过修改过后，我们需要分情况讨论：

        public void addLast(int data){
            ListNode node = new ListNode(data);
            ListNode cur = this.head;


            if(cur == null){
                this.head = node;
            }else{

                while(cur != null){
                cur = cur.next;
            }
        }

5.在指定位置插入元素(addIndex)

要在index位置插入元素，需要修改index前面元素的next值，把node位置变成后面元素的地址

操作方法：先让cur（cur为需要插入的元素的位置）走index-1步；

node.next = cur.next;? (只能先修改node的值，若是先修改的的值会导致cur.next丢失

cur.next = node;?

这是最核心的两个步骤，现在我们来完善整个代码段：
public void addIndex(int index,int data){
    if(index < 0 || index > size()){
        System.out.println("这个index不合法");
        throw new RuntimeException("这个index不合法");
    }
    
    if(index == 0){
        addFirst(data);
        return;
    }

    if(index == size()){
        addLast(data);
        return;
    }
到这里一些框架已经出来了，我们现在执行操作方法的第一步：

先让cur（cur为需要插入的元素的位置）走index-1步:
public ListNode findIndexSubOne(int index){
    ListNode cur = this.head;
    while(index - 1 != 0){
        cur = cur.next;
        index--;
    }
    return cur;
}
这里就是让cur走index-1步；

到最后，就是第二步：
ListNode cur = findIndexSubOne(data);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
完整的代码就是：

6.删除指定位置的元素

?思路很简单，代码实现略微复杂：把cur.next改成cur.next.next

cur为需要删除元素的前一个元素

怎么找到cur元素呢：
public ListNode findPreOfKey(int key){
    ListNode cur = this.head;
    while(cur.next != null){
        if(cur.next.val == key){
            return cur;
        }
    cur = cur.next;
    }
    return null;
}
如果cur.next.val == key那么就返回cur，否则就是没有这个元素

主函数：

public void remove(int key){
    if(this.head == null){
        return;
    }
    if(this.head.val == key){
        head = head.next;
        return;
    }
    ListNode cur = findPreOfKey(key);
    if(cur == null){
        System.out.println("没有你要打印的元素");
    }
    ListNode del = cur.next;//此时del也就是在被删除的元素的位置上
    cur.next = del.next;
}

最重要的就是：cur.next = del.next

del左边元素直接指向del右边元素，跳过了del元素

7.删除所有key元素（RemoveAllKey）

刚刚我们讨论了删除指定位置的元素，现在我们删除所有的key元素。（时间复杂度为O（n））

我们先定义：?cur为需要删除的元素位置，prev就是cur前面的一个元素位置

以上图为例子，key = 12，需要把所有的12删除

我们先不考虑12是头节点的情况：

当cur.val = key时
prev.next = cur.next;
cur = cur.next;
prev的next等于cur的next，那么就没有节点指向cur的位置了，只要cur = cur.next，那么这个元素就可以被删除

当cur.val != key时?
prev = cur;
cur = cur.next;
这样继续遍历下一个节点

用循环写出来:

 while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }

但如果12在头节点，我们需要改变head，使得head指向下一个元素：

        if(this.head.val == key){
            head = head.next;
        }

完整的代码就是：

    public void RemoveAllKey(int key){
        ListNode prev = this.head;
        ListNode cur = prev.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;
        }
    }

8.删除链表

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

?把头结点置为空，后置节点全部失去了指向，也就是删除链表.

9.链表面试试题

1.翻转链表（难点）

这是每年必考的题目！

解决思路：只需要将第2 3 4 5个节点分别头插到头结点的前面

我们定义head节点后面的那个为cur节点，cur后面的为curNext节点。

curNext用来保存cur后面的元素，防止修改完cur的指向后找不到cur后面的元素
ListNode cur = head.next;
head.next = null;
while(cur != null){
    ListNode curNext = cur.next;
    cur.next = head;
    head = cur;
    cur = curNext;
}
    
cur.next 等于 head，那么也就是cur指向head，也即头插

head 等于 cur，那么也就是把cur位置变成头结点，最后再cur等于curNext改变cur的位置

2.找到链表的中间结点

?采用双指针法，一个慢一个快，fast == null 或者 fast.next == null时就停下，这个时候slow正好在中间位置

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

3.链表中倒数第k个结点

思路：仍然是用双指针法，前面的指针先走k-1步，这样前后指针间隔k-1

这时前后指针同时向后走知道快的指针为null停下来，这个时候前后指针仍然间隔k-1，但是慢的指针刚好就在倒数第k个元素上：

public ListNode FindKthToTail(ListNode head, int k) {

        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0 ; i < k - 1 ; i++) {
            fast = fast.next;

        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

?但这个时候还有问题，如果k比数组的长度还要大或者k小于0，这时我们需要返回空

public ListNode FindKthToTail(ListNode head, int k) {
        if (k <= 0 || head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0 ; i < k - 1 ; i++) {
            fast = fast.next;
            if (fast == null) {  // 如果在移动k-1次的时候fast就为空了，那么就说明k太大了
                return null;
            }
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

4.合并两个链表（难点）

?合并的两个链表分别是升序的，同时要求合并完成以后要是升序的。

我们需要一个新的头结点/虚拟节点/傀儡节点，这个节点并不在链表之中，但是我们需要这样的一个节点来帮助我们找到两个头结点。

定义一个tmp = newHead 然后就是分情况讨论：

当head1<head2,我们就需要让tmp当做连接线，也即tmp.next=head1，然后head1=head1.next

head2>head1同理。最后tmp = tmp.next

while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                tmp.next = head1;
                head1 = head1.next;
            }else{
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }

这样就可以让tmp从小到大把节点连接起来。

一直到其中一个head等于null，那么就让tmp.next 等于另外一个head，这样就接上了整个的链表

    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                tmp.next = head1;
                head1 = head1.next;
            }else{
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if(head1 != null){
            tmp.next = head1;
        }
        if(head2 != null){
            tmp.next = head2;
        }
        return newHead.next; 
    }

5.链表分割(难点)? ? ? ??

现有一链表的头指针 ListNode*?pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

要把这个链表分割开，我们可以按照图中的方式，分割成前后两个链表，前面的链表的数据小于x，后面的大于x

我们设置x为33，四个数字指针代表前面链表的头和尾和后面链表的头尾。定义cur在pHead的位置。

循环结束的条件是cur = null

以图中为例子，进入循环后，

因为前面没有元素，只需要?one = cur，two = cur就行了

但如果前面已经有元素了，只需要修改two的指向就行了：
 if (two == null) {
                    one = cur;
                    two = cur;
                } else {
                    two.next = cur;
                    two = two.next;
                }
如果x比cur.val大，也是类似的写法，写在一起就是：
 while (cur != null) {
            if (cur.val < x) {
                if (two == null) {
                    one = cur;
                    two = cur;
                } else {
                    two.next = cur;
                    two = two.next;
                }
            } else {
                if (four == null) {
                    three = cur;
                    four = cur;
                } else {
                    four.next = cur;
                    four = four.next;
                }
            }
            cur = cur.next;
        }
 two.next = three;
到此核心部分已经出来了，但是还有两个问题：

1.如果x很小，所有的节点都到后面去了，也就是one和two指针都为空，那么怎么处理呢？

只要当one等于空的时候我们直接返回three就行了
        if (one == null) {
            return three;
        }
2.如果最后一个节点比x小，且倒数第二个节点比x大，那么就可能出现新链表最后的元素指向的是前面段的最后一个节点，造成死循环。处理的方法就是手动把最后一个节点置为空
        if (three != null) {
            four.next = null;
        }
完整代码：
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode one = null;
        ListNode two = null;
        ListNode three = null;
        ListNode four = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (two == null) {
                    one = cur;
                    two = cur;
                } else {
                    two.next = cur;
                    two = two.next;
                }
            } else {
                if (four == null) {
                    three = cur;
                    four = cur;
                } else {
                    four.next = cur;
                    four = four.next;
                }
            }
            cur = cur.next;
        }
        if (one == null) {
            return three;
        }
        two.next = three;
        if (three != null) {
            four.next = null;
        }
        return one;
    }
}

6.链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针Head，请返回一个bool值，代表其是否为回文结构。

思路：

1.用快慢指针把中间位置的节点找到

2.把中间结点后面的节点指向调转，从后指向前

3.前后两个指针同时往中间结点遍历，并且比较，如果一直都相同并且最后符合条件即为回文链表

第一步是找到中间结点的位置，定义fast和slow两个指针：

ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

第二步调转节点方向，我们定义：cur = slow,next? curNext = cur.next?

?让slow后面的节点指向slow，cur.next = slow,然后再让slow往后一个，cur往后一个，curNext往后一个就能完成

ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

到此就是原来slow后面的节点全部指向中间

3. 从后往前同时遍历：

 while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            head = head.next;
            slow = slow.next;
        }

前后节点的值同时比较，一直到最后两个节点重合就输出这个链表是回文的

但会出现问题，如果链表元素个数为偶数，就会出现：

head的next就是23 ,但是slow的next却是12，这会导致head和slow并不会相遇，解决办法也很简单，只需要head.next = slow时返回真就可以了

完整代码：

public boolean chkPalindrome(ListNode head) {
        // write code here
        if(head == null){
            return false;
        }
        if(head.next == null){
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        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;
        }
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

7.找两个链表公共节点

给你两个单链表的头节点?headA?和?headB?，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回?null?。

我们需要返回c1这个节点，思路如下：

1.先找到A和B的head往后遍历相遇所需的步数差

2.同时遍历，直到a和b的头相遇即停止

?先遍历两个链表，找出长度，这样就可以直到两个链表的长度差

ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0;
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        int lenB = 0;
        while(ps != null){
            lenB++;
            ps = ps.next;
        }

得到len，len就是两边的长度差

        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if(lenA - lenB < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        while(len != 0){
            len--;
            pl = pl.next;
        }

完整代码：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0;
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        int lenB = 0;
        while(ps != null){
            lenB++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if(lenA - lenB < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        while(len != 0){
            len--;
            pl = pl.next;
        }
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }

这个题比较简单，get到思路就好

8.环形链表

最后一个节点指向了中间的某个元素，这样就是环形链表。

题目一：给你一个链表的头节点?head?，判断链表中是否有环。

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

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

?用代码表示就是：
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
    return true;
}
完整代码也很简单：
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
只要是fast == slow就代表fast和slow相遇了，表示这个链表是带环的。

题目二：给定一个链表的头节点 ?head?，返回链表开始入环的第一个节点。?如果链表无环，则返回?null。

在题目一的基础上加上一些数学思想也可以轻松完成该代码

我们假设head到环的入口长度为X，环的长度为C，相遇点到环入口的长度为Y

同时我们让fast走到环的入口后，只走一圈再到相遇点

也即fast走了 X + C + (C - Y)的长度

? ? ?slow走了X + (C -Y) 的长度

但因为fast的速度是slow的两倍，所以会有fast等于两倍的slow

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 化简得：X=Y

所以在这种情况下，相遇点和head同时走，再次相遇的地点就是环的入口
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                fast = head;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }

双向链表

学习方法和单链表是一样的，通过模拟实现一个LinkedList来学习。

    static class ListNode{
        int val;
        ListNode prev;
        ListNode next;

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

val为数值，prev指向前一个节点，next指向下一个节点

head和tail分别为链表的头和尾

因为display、size、contains方法和单链表的相似，我们便不在此重复

1.头插法、尾插法：

?与单链表的头插法并不相同，当head不为空的时候我们需要修改node.next和head.prev的值

当head为空时，需要修改的不光只有head，还有tail

    public void addFirst(int data){
        ListNode node = this.head;
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

因为双链表有一定的对称性，所以尾插法和头插法比较像：

    public void addLast(int data){
        ListNode node = this.head;
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

?2.任意位置插入数据（addIndex）

?在cur前面插入时，我们需要先找到cur的位置：

    private  ListNode findIndexListNode(int index){
        ListNode cur = this.head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

然后修改相关的值，但为了防止先修改的值导致后面的数据丢失，我们先修改node.next：

        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;

完整代码：

    public void addIndex(int index,int data){
        if(index < 0 || index > size()){
            System.out.println("index不合法");
        }
        if(index == 0){
            addFirst(data);
        }
        if(index == size()){
            addLast(data);
        }
        ListNode node = new ListNode(data);
        ListNode cur = findIndexListNode(index);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    private  ListNode findIndexListNode(int index){
        ListNode cur = this.head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

2.删除元素（remove key）

?双链表中，删除元素比较复杂。

基础删除代码：

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

基础的代码以外，会遗漏的情况，需要我们自己去考虑。

情况一：删除的节点是头结点或者尾结点

       ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                if(cur == head){ //如果cur为头结点的情况，头结点等于下一个节点，原先的节点指向空
                     head = head.next;
                     head.prev = null;
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null){//cur是尾结点的情况，尾结点前移，原先节点置空
                        this.tail = cur.prev;
                        tail.next = null;
                    }else{
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur = cur.next;
            }

情况二：仅仅只有一个节点，要删除这个节点

        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                if(cur == head){
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    }else{
                        tail = null;//如果只有一个节点，那么只需要把尾结点置空就行了
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null){
                        this.tail = cur.prev;
                        tail.next = null;
                    }else{
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur = cur.next;
            }
        }

这也就是最终的代码。

3.删除所有值为key的元素

其实和删除元素很相似，只需要把return删除就行了，这样就可以反复进入链表执行操作

        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                if(cur == head){
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    }else{
                        tail = null;//如果只有一个节点，那么只需要把尾结点置空就行了
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null){
                        this.tail = cur.prev;
                        tail.next = null;
                    }else{
                        cur.next.prev = cur.prev;
                    }
                }
            }else{
                cur = cur.next;
            }
        }

4.清空链表

与单链表不同，双链表的清空并不能head和tail置空整个链表就为空，但整体比较简单，定义一个cur和curNext，一个一个置空就行了

    public void clear{
            ListNode cur = this.head;
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.next = null;
                cur.prev = null;
                cur = curNext;
            }
            head = null;
            tail = null;
        }
    }

LinkedList源代码

源代码的遍历：

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    // foreach遍历
    for (int e:list) {
    System.out.print(e + " ");
    }
    System.out.println();
    // 使用迭代器遍历---正向遍历
    ListIterator<Integer> it = list.listIterator();
    while(it.hasNext()){
    System.out.print(it.next()+ " ");
    }
    System.out.println();
    // 使用反向迭代器---反向遍历
    ListIterator<Integer> rit = list.listIterator(list.size());
    while (rit.hasPrevious()){
    System.out.print(rit.previous() +" ");
    }
    System.out.println();
}