LeetCode算法小抄 -- 链表(快慢指针、双指针、回文链表)

⚠申明： 未经许可，禁止以任何形式转载，若要引用，请标注链接地址。 全文共计10077字，阅读大概需要10分钟
🌈更多学习内容， 欢迎👏关注👀文末我的个人微信公众号：不懂开发的程序猿
个人网站：https://jerry-jy.co/

LeetCode算法小抄

Collection 子接口之 Queue (LeetCode上经常用，手撕算法题！！！)

Queue 与 Deque 的区别

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

peek函数使用

Java中的peek函数是用于取出队列中队头元素，但不会将其从队列中移除。这样，使用peek函数可以查看队列中的队头元素，而不会改变队列的状态。

例如：

Queue<Integer> queue = new LinkedList<>(); 

queue.add(1); 

queue.add(2); 

queue.add(3);

// 查看队头元素 Integer first = queue.peek(); // 返回1

// 查看队列中的元素 System.out.println(queue); // 输出[1, 2, 3]

peek函数在Java的Queue接口中定义，可以通过实现该接口的类来使用该函数。常见的实现类有LinkedList、PriorityQueue等。

使用peek函数时，需要注意以下几点：

1. 如果队列为空，peek函数会返回null，而不会抛出异常。因此，使用peek函数时，需要先判断队列是否为空，避免出现空指针异常。
2. peek函数返回的是队列中的队头元素的副本，而不是队列中的实际元素。因此，对返回的元素进行修改并不会改变队列中的实际元素。
3. 如果队列中的元素为null，peek函数也会返回null。因此，使用peek函数时，需要注意区分队列为空和队列中存在null元素的情况。
4. 如果队列中的元素为不可变对象

树

结点的度：结点拥有的子树的数目

树的度：树中结点的最大的度

满二叉树：高度为h，并且由 2^ℎ –1个结点的二叉树，被称为满二叉树，满二叉树的结点的度要么为0（叶子结点），要么为2（非叶子结点）

完全二叉树：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

二叉查找树：二叉查找树，又被称为二叉搜索树。其特点如下：设x为二叉查找树中的一个结点，x节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是 中序遍历可以让结点有序。

二叉堆和二叉树区别：

• 二叉堆在逻辑上其实是一种特殊的二叉树（完全二叉树）
• 二叉堆是存储数组，一般的链表二叉树，我们操作节点的指针，而在二叉堆里，我们把数组索引作为指针
• 二叉堆还分为最大堆和最小堆。最大堆的性质是：每个节点都大于等于它的两个子节点。类似的，最小堆的性质是：每个节点都小于等于它的子节点。

优先级队列(Priority Queue)

这种数据结构有一个很有用的功能，你插入或者删除元素的时候，元素会自动排序，这底层的原理就是二叉堆的操作。优先级队列有两个主要 API，分别是 insert 插入一个元素和 delMax 删除最大元素（如果底层用最小堆，那么就是 delMin）。

插入是先插到最后，然后上浮到正确位置；删除是调换位置后再删除，然后下沉到正确位置

放入PriorityQueue的元素，必须实现Comparable接口，没有实现Comparable接口怎么办？PriorityQueue允许我们提供一个Comparator对象来判断两个元素的顺序

面试：说一说 PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：

• PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
• PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
• PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
• PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

链表

1、单链表

递归反转

经典：206. 反转链表

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

/**
 * 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) {
        // 如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可
        if(head == null || head.next == null){
            return head;
        }
        // 递归反转
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

衍生题目：

反转链表前 N 个节点

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

/**
 * 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 reverseBetween(ListNode head, int left, int right) {
        // base case
        if(left == 1){
            return reverseN(head, right);
        }
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    // 后继节点
    ListNode successor = null;
    // 反转以 head 为起点的 n 个节点，返回新的头结点
    private ListNode reverseN(ListNode head, int n){
        if(n == 1){
            // 记录第 n + 1 个节点
            successor = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head.next = successor;
        return last;
    }
}

迭代反转

给定链表头结点，如何反转整个链表？

「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」

// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

反转 a 到 b 之间的结点

/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    // while 终止的条件改一下就行了
    while (cur != b) {
        nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

25. K 个一组翻转链表[hard]

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

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

/**
 * 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 reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        // 区间 [a, b) 包含 k 个待反转元素
        ListNode a, b;
        a = b = head;
        for(int i = 0; i < k; i++){
            // 不足 k 个，不需要反转，base case
            if(b == null) return head;
            b = b.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(a, b);
        // 递归反转后续链表并连接起来
        a.next = reverseKGroup(b, k);
        return newHead;
    }
    /** 反转区间 [a, b) 的元素，注意是左闭右开 */
    private ListNode reverse(ListNode a, ListNode b){
        ListNode pre, cur, nxt;
        pre = null; cur = a; nxt = a;
        while(cur != b){
            // 逐个结点反转
            nxt = cur.next;
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }
}

2、双链表

21. 合并两个有序链表

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

思路：

• 先初始化一个dummy = new ListNode(0) 为空的节点，定义一个ListNode p = dummy用来方便指针移动
• 如果list1 list2都不为空，作比较，小的赋值给p.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 mergeTwoLists(ListNode list1, ListNode list2) {
      // 虚拟头结点
      ListNode dummy = new ListNode(0);
      ListNode p = dummy;
      ListNode p1 = list1, p2 = list2;

      while(p1 != null && p2 != null){
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
          if(p1.val > p2.val){
             p.next = p2;
             p2 = p2.next;
          }else{
              p.next = p1;
              p1 = p1.next;
          }
          // p 指针不断前进
          p = p.next;
      }
        if(p1 != null){
            p.next = p1;
        }
        if(p2 != null){
            p.next = p2;
        }
    
    return dummy.next;
    }
}

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

/**
 * 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 partition(ListNode head, int x) {
         // 存放小于 x 的链表的虚拟头结点
        ListNode dummy1 = new ListNode(0);
        // 存放大于等于 x 的链表的虚拟头结点
        ListNode dummy2 = new ListNode(0);
        // p 负责遍历原链表，类似合并两个有序链表的逻辑
        ListNode p = head;
        // p1, p2 指针负责生成结果链表
        ListNode p1 = dummy1, p2 = dummy2;
        // 这里是将一个链表分解成两个链表
        while(p != null){
            if(p.val > x){
                p2.next = p;
                p2 = p2.next;
            }else{
                p1.next = p;
                p1 = p1.next;
            }
            // 断开原链表中的每个节点的 next 指针
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        // 连接两个链表
       p1.next= dummy2.next;
       return dummy1.next;
    }
}

23. 合并 K 个升序链表[hard]

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

这个算法是面试常考题，它的时间复杂度是多少呢？算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。

**思路：**合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？考虑使用优先队列，把k个链表加入队列中，当队列不为空，拉出一个元素，指向到p.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 mergeKLists(ListNode[] lists) {
        if(lists.length == 0){
            return null;
        }
        // 虚拟头结点
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b)->(a.val-b.val));
        // 将 k 个链表的头结点加入最小堆
        for(ListNode head : lists){
            if(head!=null){
                pq.add(head);
            }
        }
        while(!pq.isEmpty()){
             // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if(node.next != null){
                pq.add(node.next);
            }
             // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}

3、双指针类型的题目

双指针技巧主要分为两类：左右指针和快慢指针。

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

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

注意细节：又使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。

/**
 * 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 dummy = new ListNode(0);
        dummy.next = head;
        // 先找到倒数第n+1个
        ListNode x = findFromEnd(dummy, n+1);
        x.next = x.next.next;
        return dummy.next;
    }
    // 返回链表的倒数第 k 个节点
    private ListNode findFromEnd(ListNode head, int k){
        ListNode p1 = head;
        for(int i = 0; i < k; i++){
            p1 = p1.next;
        }
        ListNode p2 = head;
        while(p1 != null){
            p2 = p2.next;
            p1 = p1.next;
        }
        return p2;
    }
}

4、快慢指针的问题

876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

思路：

我们让两个指针 slow 和 fast 分别指向链表头结点 head。

每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

/**
 * 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 middleNode(ListNode head) {
        // 快慢指针初始化指向 head
        ListNode fast = head, slow = head; 
        // 快指针走到末尾时停止
        while(fast != null && fast.next != null){
            // 慢指针走一步，快指针走两步
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

判断链表是否包含环

判断链表是否包含环属于经典问题了，解决方案也是用快慢指针：

每当慢指针 slow 前进一步，快指针 fast 就前进两步。

如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。

boolean hasCycle(ListNode head) {
    // 快慢指针初始化指向 head
    ListNode slow = head, fast = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        slow = slow.next;
        fast = fast.next.next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

160. 相交链表

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

思路：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        // 计算两条链表的长度
        for(ListNode p1 = headA; p1 != null; p1 = p1.next){
            lenA++;
        }
        for(ListNode p2 = headB; p2 != null; p2 = p2.next){
            lenB++;
        }
        // 让 p1 和 p2 到达尾部的距离相同
        ListNode p1 = headA, p2 = headB;
        if(lenA > lenB){
            for(int i = 0; i < lenA -lenB; i++){
                p1 = p1.next;
            }
        } else {
            for(int i = 0; i < lenB - lenA; i++){
                p2 = p2.next;
            }
        }
        // 看两个指针是否会相同，p1 == p2 时有两种情况：
        // 1、要么是两条链表不相交，他俩同时走到尾部空指针
        // 2、要么是两条链表相交，他俩走到两条链表的相交点
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

5、回文链表

寻找回文串

核心思想是从中心向两端扩展

因为回文串长度可能为奇数也可能是偶数，长度为奇数时只存在一个中心点，而长度为偶数时存在两个中心点，所以上面这个函数需要传入 l 和 r。

// 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
String palindrome(String s, int left, int right) {
    // 防止索引越界
    while (left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        // 双指针，向两边展开
        left--;
        right++;
    }
    // 返回以 s[left] 和 s[right] 为中心的最长回文串
    return s.substring(left + 1, right);
}

判断一个字符串是不是回文串

因为回文串是对称的，所以正着读和倒着读应该是一样的，这一特点是解决回文串问题的关键。

boolean isPalindrome(String s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

这道题的关键在于，单链表无法倒着遍历，无法使用双指针技巧

1、最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同

/**
 * 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 boolean isPalindrome(ListNode head) {
        ListNode head2 = reverseList(head);
        while(head2 != null && head != null){
            if(head.val != head2.val) return false;
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }
    private ListNode reverseList(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

2、其实，借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表

3、快慢指针，降低空间复杂度

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步：
        if(fast != null){
            slow = slow.next;
        }
        // 从slow开始反转后面的链表，现在就可以开始比较回文串了
        ListNode left = head;
        ListNode right = reverse(slow);
        while(right != null){
            if(left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }
    // 迭代反转
    private ListNode reverse(ListNode head){
        ListNode pre = null, next = null, cur = head;
        while (cur != null) {
            next = cur.next;
            // 逐个结点反转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = next;
        }
    // 返回反转后的头结点
    return pre;
    }
}

总结：

首先，寻找回文串是从中间向两端扩展，判断回文串是从两端向中间收缩。对于单链表，无法直接倒序遍历，可以造一条新的反转链表，可以利用链表的后序遍历，也可以用栈结构倒序处理单链表。

具体到回文链表的判断问题，由于回文的特殊性，可以不完全反转链表，而是仅仅反转部分链表，将空间复杂度降到 O(1)。

–end–文章来源地址https://www.toymoban.com/news/detail-404940.html

到了这里，关于LeetCode算法小抄 -- 链表(快慢指针、双指针、回文链表)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！