代码随想录——链表

一、基础知识

1. 线性表的顺序表示

• 地址连续
• 依次存放
• 随机存取
• 类型相同

和数组的定义是一致的，所以用一维数组表示顺序表。但是线性表长可变（删除），数组长度不可动态定义

2. 线性表的链式表示（链表）
   ① 结点：数据元素的存储映像，由数据域和指针域两部分组成。
   ② 链表：n个结点由指针链组成一个链表
   它是线性表的链式存储映像，称为线性表的链式存储结构
   ③ 单链表、双链表、循环链表
   结点只有一个指针域的链表，称为单链表或线性链表。
   结点有两个指针域的链表，称为双链表（两个指针域分别指向前驱元素地址和后继元素地址）
   首尾相接的链表称为循环链表。
   ④ 头指针、头节点和首元结点
   头指针：是指向链表中第一个结点的指针。
   首元结点：是指链表中存储第一个数据元素的结点。
   头节点：是在链表的首元结点之前附设的一个结点。
   ⑤ 在链表中设置头节点的好处
   ⑥ 链表（链式存储结构的特点）

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
• 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。这样称为顺序存取的存取结构。注：顺序表：随机存取

3. 单链表
   3.1 定义和表示
   3.2 基本操作的实现

• 单链表的初始化
• 判断链表是否为空
  空表：链表中无元素，称为空链表（头指针和头节点仍然在）
  算法思路：判断头结点指针域是否为空
• 单链表的销毁
  算法思路：从头指针开始，依次释放所有结点。先将头结点的指针赋值给头指针，则头指针现在就指向首元结点了，然后删除头结点，依次进行下去。
• 清空链表
  （链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍在））
  算法思路：依次释放所有结点，并将头结点指针域设置为空。
• 求单链表的表长
• 取值——取单链表中第i个元素的内容
• 查找——按值查找（根据指定数据获取该数据所在的位置（地址））
• 插入——在第i个结点前插入值为e的新结点
• 删除——删除第i个结点
• 建立单链表——头插法（元素插在链表头部）

3.3 查找、插入、删除算法时间效率分析

• 查找：因线性链表只能顺序存取，即在查找是要从头指针找起，查找的时间复杂度为O(n)
• 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。

二、移除链表元素（203 简单）

题目描述：给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val==val的节点，并返回新的头节点 。

我们认为链表由头指针、头结点、首元结点组成。因为链表是顺序存取的，所以想要移除链表中的元素，肯定要从头结点根据地址一个个的往下查找，当遇到val时删除该结点。这种情况下的移除操作，就是让节点next指针直接指向下一个节点就可以了。

代码一：

算法思路：

1. cur结点
   cur.next指针（也就是下一个结点的地址）
   cur.val值
   （其中val和next都是链表ListNode中定义的属性）
2. 为什么要设置一个虚拟结点，如果没有虚拟结点，因为链表是顺序存取，那么第一个元素没办法删掉。
3. 已知链表head，再new一个新的链表dummy（增加一个虚拟结点，即头结点，随便赋值即可）。然后赋值令pre=dummy，cur=head（赋值时赋的都是地址值，当pre变了，dummy也变了）。下面因为一定存在循环，所以应该考虑循坏条件判断语句：当cur等于null时结束算法，所以while（cur！=null），所以应该更新cur=cur.next。如果cur.val == val，因为pre是在cur的前一个的，所以当cur.val等于val，pre.next就应该跳过cur，等于cur.next；反之，如果cur.val不等于val，那么pre=cur
4. 如果不等，那么更新pre为cur；如果相等，那么pre的指针pre.next就改变为cur.next.
   如果我们不设置虚拟节点的话，那么头结点是无法被移除的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。也就是头结点是无法被改变的，因为没有指针指向头结点，所以设置一个虚拟结点，这时头结点如果为val就可以被移除了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //定义方法removeElements，返回ListNode型的，即返回链表
    //所以在刷leetcode的时候，链表的节点都默认定义好了，直接用就行了，直接写方法
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
        }
        //new一个新的对象，让它前面有一个虚拟结点，所以对dummy进行一系列操作即可，
        //元首结点的值就也可以判断了
        ListNode dummy=new ListNode(-1,head);//两个参数的构造器
        //定义两个结点并给他们赋值
        ListNode pre=dummy;
        ListNode cur=head;

        while(cur!=null){
            if(cur.val==val){
                pre.next=cur.next;
            }else{
                pre=cur;
            }
            cur=cur.next;
        }
        return dummy.next;  
    }       
}

代码二：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
        }
        //new一个新的对象，让它前面有一个虚拟结点，所以对dummy进行一系列操作即可，
        //元首结点的值就也可以判断了
        ListNode dummy=new ListNode(-1,head);//两个参数的构造器
        //定义两个结点并给他们赋值
        ListNode pre=dummy;
        ListNode cur=head;

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


        return dummy.next;  
    }    
}

注：移除链表元素的中心思想其实是删除链表中的元素。

三、设计链表（707 中等）

注：1. index从0开始，即当index=0时，获取链表的第一个结点
2.

//单链表
class ListNode{
    int val;
    ListNode next;

    public ListNode(){

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


class MyLinkedList {
    //定义两个属性：存储链表元素的个数和虚拟头结点
    int size;
    ListNode head;

    //初始化链表
    public MyLinkedList() {
        size=0;
        head=new ListNode(0);//构造器
        //head是带有虚拟头结点的链表，虚拟头结点的数值为0

    }

    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        //如果下标无效，则返回-1
        if(index<0||index>=size){
            return -1;
        }
        ListNode cur=head;//设一个cur临时结点，让它循环
        //查找
        //因为index从0开始，当index=0时，查找的是链表的第一个结点（不包括虚拟头结点时），所以是i<=index
        for(int i=0;i<=index;i++){
            cur=cur.next;
        }
        return cur.val;

    }
    //将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
    public void addAtHead(int val) {
        addAtIndex(0,val);

    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);

    }
    //将一个值为 val 的节点插入到链表中下标为 index 的节点之前
    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<0){
            index=0;
        }
        size++;
        //找到要插入结点的前一个位置
        ListNode cur=head;
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        ListNode toAdd=new ListNode(val);
        toAdd.next=cur.next;
        cur.next=toAdd;
    }
    //删除第i个结点
    public void deleteAtIndex(int index) {
        if(index<0||index>=size){
            return;
        }
        
    
        ListNode cur=head;
        //找到第index-1个结点
        for(int i=0;i<index;i++){
            cur=cur.next;
        }
        cur.next=cur.next.next;
        size--;


    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

四、反转链表（206 简单）

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

4.1 双指针法

1. 算法思路
   

2. 注：
   ① 初始化使令pre为空指针null，也就是最后反转成功的链表的最后一位是空指针。这里的pre其实是用来存储我们要获得的指针。
   ② “=”的作用经常理解不清楚，“=”理解为赋值。
   ③ 使用临时指针存储cur的下一个元素的地址，是为了让cur和pre前进
   ④

3. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
        ListNode pre=null;
        ListNode temp=null;
        while(cur!=null){
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}

4.2 递归法

1. 思路和双指针法是一样的，写一个反转的reverse方法，传入形参cur和pre，在reverse方法里调用reverse方法（递归），使用reverse方法返回反转后的链表。
2. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head,null);
    }

    private ListNode reverse(ListNode cur,ListNode pre){
        if(cur==null){
            return pre;
        }
        ListNode temp=null;
        temp=cur.next;
        cur.next=pre;
        return reverse(temp,cur);
    }
}

五、两两交换链表中的节点（24 中等）

题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

5.1 法一

1. 算法思路
   
2. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy=new ListNode(0,head);//dummy是虚拟头结点
        ListNode cur=dummy;
        ListNode pre=head;
        ListNode temp;
        while(cur.next!=null&&cur.next.next!=null){
            temp=pre.next.next;
            cur.next=pre.next;
            pre.next.next=pre;
            pre.next=temp;
            //更新（前进）cur pre
            cur=pre;
            pre=temp;

        }
        return dummy.next;
    }
}

3. 注：
   ① 需要特别注意算法的终止条件：因为可能有两种情况，一种情况是链表中有偶数个数据元素，另一种情况是链表中有奇数个数据元素。因为cur必须指向两个要交换的数据元素的前一个元素，所以如图所示，当cur.next等于null或cur.next.next等于null时循环终止
   
   ② 注意pre和cur前进应该被赋值为哪一个：由算法思路的图可以看出，1这个数据元素应该赋值给cur，在链表中我们关注地址值是一定不会出错的，所以就是1的地址赋值给cur，即pre；给pre更新同理

5.2 法二：递归

1. 思路：在swapPairs这个方法里调用该方法
   

2. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        //递归结束条件：头节点不存在或头节点的下一个节点不存在。此时不需要交换，直接返回head
        if(head==null || head.next==null){
            return head;
        }
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;

        return next;
    }
}

3. 注意：
   ① 递归方法不需要设置虚拟头结点，在思路上和上面的循环还不一样

六、删除链表的倒数第N个结点（19 中等）

题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

1. 算法思路：
   ① 找到倒数第N+1个结点，这道题的关键也是找到倒数第N+1个结点，如果要删除第一个结点呢？所以要设置虚拟头结点。
   

② 如何解决找到倒数第N+1个结点：设置一个fast指针和一个slow指针，开始时令慢指针指向虚拟头结点，快指针指向头结点，当快指针走N-1步慢指针此时移动，直到快指针为null

2. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyhead=new ListNode(0,head);//虚拟头结点；
        ListNode fast=head;
        ListNode slow=dummyhead;
        for(int i=0;i<n;i++){
                fast=fast.next;
            }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        //找到倒数第N+1个数据元素了，下面删除
        slow.next=slow.next.next;
        return dummyhead.next;
    }
}

3. 注意：
   ①

while(fast!=null){
            for(int i=0;i<n;i++){
                fast=fast.next;
            }
            slow=slow.next;
            fast=fast.next;
        }

如上代码错误：因为只要出了for循环，slow和fast都需要前进，然后在进入while，进入for，显然错误。
　　② 返回dummyhead.nex，不能返回head，有可能被删掉的是head

七、链表相交（面试题 02.07. 链表相交）

7.1 法一

思路：因为如果两个链表有交点，则从某一个数据元素开始以后的数据元素都是相同的，所以我们以从后往前的眼光看待，如下图所示，所以需要得到链表A和B的长度，计算它们的差，然后令其中短链表的指针从头结点开始，长链表的指针从与其对齐的位置开始，则下面判断curA.next是否等于curB.next即可（中心思想：看作两个长度相等的链表是否有交点）。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA=headA;
        ListNode curB=headB;
        //计算链表A的长度
        int lenA=0;
        int lenB=0;
        while(curA!=null){
            lenA++;
            curA=curA.next;
        }
        //计算链表B的长度
        while(curB!=null){
            lenB++;
            curB=curB.next;
        }
        curA=headA;
        curB=headB;
        // 让curB为最长链表的头，lenB为其长度;如果A更长，则交换
        if(lenA>lenB){
            int temp=lenB;
            lenB=lenA;
            lenA=temp;
            ListNode tmpNode = curB;
            curB = curA;
            curA = tmpNode;
        }
        int gap=lenB-lenA;
        for(int i=0;i<gap;i++){
            curB=curB.next;
        }
        while(curA!=curB){
            curA=curA.next;
            curB=curB.next;
        }
        return curA;
    }
}

7.2 法二

同样利用双指针，考虑在相交结点处相遇。指针A在链表A的头结点出发走完链表A，然后从链表B的头结点走完第③段；指针B在链表B的头结点出发走完链表B，然后从链表A的头结点走完第③段。则指针A和指针B走过的距离均为$a+b+c$，所以它们在相交结点处相遇，所以得到相交结点。和下面一题环形链表都是相遇问题。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA=headA;
        ListNode curB=headB;
        while(curA!=curB){
            curA=curA==null ? headB : curA.next;
            curB=curB==null ? headA : curB.next;
        }
        return curA;
    }
}

注：

while(curA!=curB){
            curA=curA ? curA.next:headB;
            curB=curB ? curB.next:headA;
        }

这样会报错： listnode cannot be converted to boolean，因为三元运算符curA=curA ? curA.next:headB中curA不是boolean类型的，是ListNode类型

八、环形链表（142 中等）

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

2. 算法思路（双指针法）：
① 设置快指针fast，慢指针slow，快指针每次前进两个结点，慢指针每次前进一个结点。如果存在环，那么快慢指针一定会在环内相遇，因为快慢指针相对速度为1个结点。
② 当慢指针开始进入环，追击开始，此时快指针可能已经在环内转了好多圈了，因为相对速度是1，所以快指针一定能追上慢指针，并且从慢指针进入环开始计算，快指针不需要一圈就能追击上（因为相对速度，相当于慢指针静止，快指针以1个结点的速度运动）。不以相对距离的眼光去看的话，快慢指针相遇时，慢指针一定没有转完一整圈，快指针至少转了一整圈。
③ 根据以上分析，数学公式如下：

慢指针走过的结点数：$x+y$
快指针走过的结点数：$x+n(y+z)+y$
快慢指针走过的结点数可以看作它们走过的距离，快指针每次前进两个结点，慢指针每次前进一个结点，所以在相同时间内：
$$\begin{array}{r}x+y=\frac{x+n(y+z)+y}{2}\\ 2(x+y)=x+n(y+z)+y\end{array}$$
整理得：
$$\begin{array}{r}x=(n?1)(y+z)+z\end{array}$$
这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是环形入口的节点。
④ 从追击相遇的物理问题角度加深理解，只考虑$n=1$的情况。
因为慢指针每次前进一个结点，并且当慢指针到达环形链表起点的时候，追击问题开始，不妨设此时时间为x，则快指针走过的路程为2x，所以此时快指针在环里走了大小为x的路程，其他分析见下图

3. 代码
上面分析了对问题的理解及建模，下面考虑代码的思路。由这句话“这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是环形入口的节点。”首先找到相遇结点，然后从头结点和相遇结点设置两个指针，相遇的结点即为环形入口的结点，想法很简单，也容易实现，稍微困难的是判断环是否存在。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    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){
                ListNode index1=head;
                ListNode index2=fast;
                while(index1!=index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}