JAVA链表基础——代码随想录 链表

JAVA链表基础

基础知识

定义

  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; }
  }

链表的存储方式

节点由val域（数据域），以及next域（指针域）组成，对于next域，其是引用类型，存放下一个节点的地址，故用public ListNode next来创建next。

Leetcode 203. 移除链表元素

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

• 一开始的思路：
  • 使用两个指针，一个在前一个在后，删除结点使用q -> next = p -> next删除p
  • 发现头结点删不掉，设置一个新的结点指向头结点
• 难点：
  • 不会初始化结点（笑死）,ListNode dummy = new ListNode(-1, head);
  • next和val用.不用->

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1, head);
        
        ListNode q = dummy;
        ListNode p = head;
        while(p != null){
            
            if(p.val == val){
                q.next = p.next;
            }
            else{
                q = p;
            }
            p = p.next;
        }
        return dummy.next;
    }
}

Leetcode 707.设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
• 单链表

class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val = val;
    }
}
class MyLinkedList {

    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode dummy;

    public MyLinkedList() {
        dummy = new ListNode(0); 
        size = 0;
    }
    
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        
        ListNode p = dummy;
        for(int count = 0; count <= index; count++){
            p = p.next;
        }
        return p.val;
        
    }
    
    public void addAtHead(int val) {
    	addAtIndex(0, val);  
    }
    
    public void addAtTail(int val) {
    	addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index < 0){
            index = 0;
        }
        if(index > size){
            return;
        }
        
        ListNode p = dummy;
        for(int count = 0; count < index; count++){
            p = p.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = p.next;
        p.next = newNode;
        size++;  
    }

    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }
        if(index == 0){
            dummy = dummy.next;
            size--;
            return;
        }

        ListNode p = dummy;
        for(int count = 0; count < index; count++){
            p = p.next;
        }
        p.next = p.next.next;
        size--;
 
    }
}

• 双链表

class ListNode {
    int val;
    ListNode next, pre;
    ListNode(){}
    ListNode(int val) {
        this.val = val;
    }
}
class MyLinkedList {

    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head, tail;

    public MyLinkedList() {
        head = new ListNode(0);
        tail = new ListNode(0);
        head.next = tail;
        tail.pre = head;
        size = 0;
    }
    
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        
        ListNode p = head;
        for(int count = 0; count <= index; count++){
            p = p.next;
        }
        return p.val;
        
    }
    
    public void addAtHead(int val) {
    	addAtIndex(0, val);  
    }
    
    public void addAtTail(int val) {
    	addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index < 0){
            index = 0;
        }
        if(index > size){
            return;
        }
        
        ListNode p = head;
        for(int count = 0; count < index; count++){
            p = p.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = p.next;
        newNode.pre = p;
        p.next.pre = newNode;
        p.next = newNode;
        size++;  
    }

    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }

        ListNode p = head;
        for(int count = 0; count < index; count++){
            p = p.next;
        }
        p.next.next.pre = p;
        p.next = p.next.next;
        size--;
    }
}

• 单链表双链表的差距在于添加删除结点时，一个只处理next指针，一个需处理next和pre指针

Leetcode 206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

• 一开始的思路：头插法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        while(p != null){

            ListNode temp = new ListNode(p.val);
            temp.next = dummy.next;
            dummy.next = temp;
            p = p.next;
        }
        return dummy.next;

    }
}

• 题解：如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

• pre要初始化为null

Leetcode 24.两两交换链表中的节点

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

• 一开始的思路：设置两个指针去移动，后来发现多余了，只需要一个指针

• 题解：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pUMaszbg-1669598313009)(https://code-thinking.cdn.bcebos.com/pics/24.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B91.png)]

class Solution {
    public ListNode swapPairs(ListNode head) {
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null){
            ListNode rest = cur.next.next.next;
            ListNode temp = cur.next;
            cur.next = cur.next.next;
            cur.next.next = temp;
            cur.next.next.next = rest;
           
            cur = cur.next.next;
        }
        return dummy.next;
    }
}

注意：

• 难点在于next指针移动后， 会找不到接下来的结点，所以要设置临时结点保存

Leetcode 19.删除链表的倒数第N个节点

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

• 一开始的思路：
  • 遍历两遍，但是时间复杂度太高，隐约想到用双指针法，但是没想到怎么设置两个指针
• 题解：
  • 设置slow和fast两个指针
  • 删除结点时指针需指向被删结点的前一个结点
• 注意：倒数n个，是怎么利用数字实现的

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        int count = n;
        while(n > 0){
            fast = fast.next;
            n--;
        }

    //     for (int i = 0; i < n  ; i++){
    //     fast = fast.next;
    // }

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

LeetCode 面试题 02.07. 链表相交

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

图示两个链表在节点 c1 开始相交**：**

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）

• 一开始的思路：

  • 暴力双循环（达咩德斯）
  • 双指针法，一个指向a一个指向b，但是没想好怎么去比较

• 题解：

  • 读懂题目，题目找的是两个链表相交，意思是从那一个结点开始，后面全部相交，所以不存在链表a的中间与链表b的全部相交这种情况。
  • 所以，应该从尾部对齐，然后一个一个元素对比，只要第一个元素相同，后面就不用比较了，就一定相同（题目就是这个意思）。
  • carl写的里面要交换lengtha和lengthb，我觉得不是实现的必要步骤。我思考了一下为什么要swap (lenA, lenB)和swap (curA, curB)。其实不交换是可以的，不影响流程。交换cura和curb是让a指向长的链表，然后直接用一个while循环gap自减去移动指针，如果交换的话还需要在下面做一个判断谁长然后移动谁。lenA, lenB同理，交换以后gap一定为正数，就不用取绝对值了。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        int lengtha = 0;
        int lengthb = 0;
        while(a != null){
            lengtha++;
            a = a.next;
        }
        while(b != null){
            lengthb++;
            b = b.next;
        }

        a = headA;
        b = headB;
        int gap = 0;
        if(lengthb > lengtha){
            ListNode temp = a;
            a = b;
            b = temp;
            gap = lengthb - lengtha;
        }
        else{
            gap = lengtha - lengthb;
        }
        
        while(gap > 0){
            a = a.next;
            gap--;
        }

        while(a != null){
            if(a == b){
                return a;
            }
            a = a.next;
            b = b.next;
        }
        return null;

    }
}

LeetCode 142. 环形链表 II

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

• 一开始的思路：
  • 最好的情况是只遍历一遍，用两个指针？为啥我一开始就会想到双指针法一个快一个慢？
  • 有环时，一个结点可以通过两个路径到达？出现环的结点一定是最后一个结点吗？一个指针只有一个next，如果他指向下一个结点的话就不可能指向前面的结点。最后一个结点的说法其实是错误的，环哪有最后一个的说法？
• 题解：
  • 双指针判断是否有环，没有环时快指针永远不可能与慢指针相遇。如果快指针一次走两格，慢指针一次走一格，快相对于慢是每次一一格的速度去追赶慢指针，一定会相遇，如果快指针一次走三格说不一定就永不相遇。
  • [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oT394qoz-1669598313010)(C:\Users\wsco24\AppData\Roaming\Typora\typora-user-images\image-20221126182307157.png)]
    • fast首先进入环，并且移动了y距离
    • slow此时并没有进入环，并且距离相遇点还有x距离。
    • 继续移动，fast和slow相遇时，slow又移动了x距离，fast又移动了z + (y + z) * n的距离，n为fast在环里循环的圈数。
    • 可列出等式： x + y = x + y + (y + z) * n，化简得出：x = (n - 1) * (y + z) + z。如果只转了一圈的话，x=z。
    • 最后利用index1与index2模拟最后一段路程找到入环结点

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