[数据结构与算法]力扣周结02

跟着卡哥的刷题路线，本周的力扣周结没有迟到！本周完成了链表模块和部分哈希表模块，我这里将链表模块总结出来，因为总结的目的在于对旧知识点的回顾。哈希表最近几天才刷

203. 移除链表元素

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

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

解题思路

删除链表的关键是找到需要删除结点的前一个结点，通过改变前一个结点的指向来删除链表元素，本题中因为链表头指针可能为空所以为了考虑到特殊情况，我们设置一个虚拟头节点，虚拟头节点这个思路很重要，在涉及到删除链表元素的时候往往使用虚拟头结点会事半功倍

核心代码

/**
 * 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) {
        ListNode dummyHead = new ListNode(0); // 设置虚拟头结点
        dummyHead.next = head; // 让虚拟头结点连接链表
        ListNode temp = dummyHead; // 指定一个指针用来遍历链表
        while (temp.next != null) {
            if (temp.next.val == val) { // 判断当前结点的下一个结点的值是否是需要删除结点
                temp.next = temp.next.next; // 如果是就让这个结点的next指针指向下下个结点
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next; // 返回头结点
    }
}

时间复杂度

O(n)，时间规格和链表长度有关

空间复杂度

O(1)

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 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

• 所有val值都在 [1, 1000] 之内。
• 操作次数将在 [1, 1000] 之内。
• 请不要使用内置的 LinkedList 库。

解题思路

模拟题比较常规，值得注意的是对于细节的把握，思路不难做对不容易

核心代码

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 MyLinkedList {
    // 表示链表的长度
    int size;
    // 设置一个虚拟头结点
    ListNode head;
    
    // 题目要求无参构造，初始化值
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    // 获取链表中索引 index 节点的值。如果索引无效，则返回-1
    public int get(int index) {
        if(index < 0 || index >= size) { // 判断索引值是否超出范围
            return -1;
        }
        ListNode ref = head;
        for(int i = 0; i < index; i++) {
            ref = ref.next;
        }
        return ref.next.val;
    }

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

    // 将值为 val 的节点追加到链表的最后一个元素
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) {
            return;
        }
        if(index < 0) {
            index = 0;
        }
        ListNode ref = head;
        for(int i = 0; i < index; i++) {
            ref = ref.next;
        }
        ListNode temp = new ListNode(val);
        temp.next = ref.next;
        ref.next = temp;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        // 如果索引 index 有效，则删除链表中的第 index 个节点
        if(index < 0 || index >= size) {
            return;
        }  
        ListNode ref = head;
        for(int i = 0; i < index; i++) {
            ref = ref.next;
        }
        ref.next = ref.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. 反转链表

这道题很经典了，我见过很多面试题中都有这道题

解题思路

1. 递归，画图，将递归的过程想成入栈和出栈
2. 双指针，快慢双指针，用一个临时变量temp存储fast指向的下一个元素，然后让fast和slow实现局部反转，再让fast指向临时变量，直到fast为空表示链表遍历结束

核心代码

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

双指针

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) { // 如果头节点为空或者头结点的下一个结点为空都代表链表不需要反转
            return head;
        }
        ListNode slow = head, fast = head.next; // 让慢指针指向头结点，让快指针指向头结点的下一个结点
        while(fast != null) { // 循环结束的条件为fast的为空
            ListNode temp = fast.next; // 临时变量存储fast的下一个结点，便于下一次循环
            ListNode node = fast; // 9到12行表示快慢指针的局部转换
            fast.next = slow;
            slow.next = null;
            slow = node;
            fast = temp; // 转换完毕后slow指向fast的位置，让fast指向之前存储的临时变量的位置便于下次循环
        }
        return slow;
    }
}

时间复杂度

递归 O(n)

双指针 O(n)

空间复杂度

递归 O(n)

双指针 O(1)

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

解题思路

需要两两交换结点，让头结点的下一个结点指向头结点，并让头结点指向下一次递归返回的头结点，画图！

核心代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
         ListNode temp = head.next;
         head.next = swapPairs(temp.next);
         temp.next = head;
         return temp;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

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

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

解题思路

这是双指针的巧用之一，假设链表长度为x，先让快指针先走n步，那么剩下的路就是x-n，此时快慢指针同速移动，当快指针走到链表结尾时快指针也走了x-n步剩下的长度为x-(x-n) = n，慢指针所在结点就是倒数第n个结点

核心代码

/**
 * 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 ref = new ListNode(0, head); // 设置虚拟头结点
        ListNode fast = ref;
        ListNode slow = ref;
        for(int i = 0; i < n; i++) { // 先让快指针先走n步
            fast = fast.next;
        }
        while(fast != null && fast.next != null) { // 快慢指针同速移动直到快指针走到头
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next; // 删除倒数第n个结点
        return ref.next;
    }
}

时间复杂度

O(n)

空间复杂度

O(1)

面试题 02.07. 链表相交

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

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

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

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

示例 1：

输入：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 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

解题思路

将其中一个链表遍历一遍存储到哈希表中，然后遍历第二个结点如果第二个结点中有与第一个结点相同的代表找到了相交点

核心代码

/**
 * 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) {
        HashSet<ListNode> set = new HashSet<>();

        ListNode nodeA = headA;
        ListNode nodeB = headB;

        while(nodeA != null) { // 遍历结点存储到哈希表中
            set.add(nodeA);
            nodeA = nodeA.next;
        }

        while(nodeB != null) {
            if(set.contains(nodeB)) { // 这两步代码初看很懵逼为啥啊？起始不仅仅比较的是结点的val和next还要比较结点的地址
                return nodeB;
            } else {
                nodeB = nodeB.next;
            }
        }
        return null;
    }
}

空间复杂度

O(n)

时间复杂度

O(n)

142. 环形链表 II

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

解题思路

巧用快慢指针

核心代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next; // 慢指针走一步，快指针走两步，如果有环那么快慢指针一定相遇！
            fast = fast.next.next;

            if(slow == fast) { // 如果相遇了代表有环因为题目要求要求环的起点
                slow = head; // 让慢指针重新指向头结点
                while(fast != slow) {
                    slow = slow.next; // 在两指针不相遇时同速移动
                    fast = fast.next;
                }
                return slow; // 返回起点
            }
        }

        return null;
    }
}

时间复杂度

O(n)

空间复杂度

O(1)