算法刷题笔记 Day_1 7道链表题

╰+攻爆jí腚メ 2024-03-26 14:10 115阅读 0赞

### 链表算法 ###

**目录**

链表算法

1.合并两个有序链表

2.单链表的分解

3.合并 k 个有序链表

4.单链表的倒数第 k 个节点

5.单链表的中点

6.判断链表是否包含环

7.两个链表是否相交

--------------------

#### 1.合并两个有序链表 ####

最基本的链表技巧，力扣第 21 题「 [合并两个有序链表][Link 1]」

给你输入两个有序链表，请你把他俩合并成一个新的有序链表，函数签名如下：

ListNode mergeTwoLists(ListNode l1, ListNode l2);

这题比较简单，我们直接看解法：

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = l1, p2 = l2;
        
        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;
    }

**代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 `dummy` 节点**，它相当于是个占位符，可以避免处理空指针的情况，降低代码的复杂性。

#### 2.单链表的分解 ####

力扣第 86 题「 [分隔链表][Link 2]」

class Solution {
        public ListNode partition(ListNode head, int x) {
        ListNode font = new ListNode(-1),fontRest = font;
        ListNode end = new ListNode(-1),endRest = end;
        while (head!=null){
            if (head.val < x){
                font.next = head;
                font = font.next;
            }else {
                end.next = head;
                end = end.next;
            }
    //        head = head.next;
            //断层操作 断开head链表中该结点和下个结点的联系
            ListNode temp = head.next;
            head.next = null;
            head = temp;
        }
                font.next = endRest.next;
            return fontRest.next;
        }
    }

在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 `x`，另一个链表中的元素都大于等于 `x`，最后再把这两条链表接到一起，就得到了题目想要的结果.

**关键点**：在遍历head结点的时候，外面要注意将head结点掐断一下，防止head.next的数据被全部赋值到font或者是end两个链表中，我们在每一次（分割链表）遍历的过程中，都需要断层处理，保证我们每次只处理一个数据！

#### 3.合并 k 个有序链表 ####

力扣第 23 题「 [合并K个升序链表][K]」

ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        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;
    }

这里有个重要知识点：**二叉堆的优先队列**

参考资料链接：

[二叉堆详解实现优先级队列 :: labuladong的算法小抄][_ labuladong]

[优先级队列PriorityQueue\_优先队列 poll\_秋鸣之时的博客-CSDN博客][PriorityQueue_ poll_-CSDN]

//优先队列 PriorityQueue类实现方法：
    public class PriorityQueue<E>
    extends java.util.AbstractQueue<E>
    implements java.io.Serializable

基于**优先级堆**的无限**优先级队列**。优先级队列的元素根据它们的**自然顺序进行排序**，或者由队列构建时提供的比较器进行排序，具体取决于使用的构造函数。优先级队列不允许空元素。依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致ClassCastException）。 此队列的头部是与指定排序相关的最少元素。如果多个元素以最小值绑定，则头部是这些元素中的一个——绑定被任意断开。队列检索操作轮询、删除、偷看和元素访问队列头部的元素。 优先级队列是无限的，但它有一个内部容量来控制用于存储队列中元素的数组的大小。它总是至少与队列大小一样大。当元素添加到优先级队列中时，其容量会自动增长。未指定增长政策的详细信息。 此类及其迭代器实现Collection和iterator接口的所有可选方法。方法迭代器（）中提供的迭代器不能保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用Arrays.sort（pq.toArray（））。 请注意，此实现不同步。如果任何线程修改队列，则多个线程不应同时访问PriorityQueue实例。而是使用线程安全的java.util.concurrent.PriorityBlockingQueue类。

**实现说明**：此实现为入队和出队方法（offer、poll、remove（）和add）提供了O（log（n））时间；移除（Object）和包含（Object）方法的线性时间；以及检索方法（peek、元素和大小）的恒定时间。 此类是Java集合框架的成员。

**lambda**表达式写法

如下lambda表达式：

(int a,int b)->  {return a + b;}

如上，本质是一个函数。  
一般的函数如下：

int add(int a,int b){
    return a + b;
    }

**有返回值，方法名，参数列表，方法体**

lambda表达式只有**参数列表**和**方法体**：

(参数列表) -> {
    方法体;
    }

#### 4.单链表的倒数第 k 个节点 ####

只遍历了一次链表，就获得了链表倒数第 `k` 个结点。（更加高级！）

（普通方法：遍历两次 然后得到值）

// 返回链表的倒数第 k 个节点
    ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1 先走 k 步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        // p1 和 p2 同时走 n - k 步
        while (p1 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
        return p2;
    }

相关例题：力扣第 19 题「 [删除链表的倒数第 N 个结点][N]」

class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode ListDeleteNode = findFromEnd(dummy, n + 1);
            ListDeleteNode.next = ListDeleteNode.next.next; //删除操作!
            return dummy.next;
        }
        // 返回链表的倒数第 k 个节点
        ListNode findFromEnd(ListNode head, int k) {
            ListNode point = head;
            //先让point走k步
            for (int i = 0; i < k; i++) {
                point = point.next;
            }
            while (point != null) {//两指针同时往后面走
                head = head.next;
                point = point.next;
            }
            return head;
        }
    }

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

但有了我们虚拟节点 `dummy` 的存在，就避免了这个问题，能够对这种情况进行正确的删除

#### 5.单链表的中点 ####

力扣第 876 题「 [链表的中间结点][Link 3]」，问题的关键是我们无法直接得到单链表的长度 `n`，**常规方法**也是先遍历链表计算 `n`，再遍历一次得到第 `n / 2` 个节点，也就是中间节点。这样做比较呆，下面看**巧妙解法**：

使用「**快慢指针**」的技巧：

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

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

上述思路的代码实现如下：

class Solution {
        public ListNode middleNode(ListNode head) {
            //初始化 快指针 和 慢指针
            ListNode slow = head,fast = head;
            while (fast!=null&&fast.next!=null){// 快指针走到末尾时停止
                // 慢指针走一步，快指针走两步
                fast =fast.next.next;
                slow = slow.next;
            }
            //此时慢指针走到中点了
            return slow;
        }
    }

如果链表长度为**偶数**，也就是说中点有两个的时候，我们这个解法返回的节点是靠后的那个节点。

另外，这段代码稍加修改就可以直接用到判断链表成环的算法题上。

#### 6.判断链表是否包含环 ####

解决方案也是用**快慢指针**：

每当慢指针 `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;
    }

这个问题还有**进阶版**：如果链表中含有环，如何计算这个**环的起点**？

解法代码：具体查看 [双指针技巧秒杀七道链表题目 :: labuladong的算法小抄][_ labuladong 1]

#### 7.两个链表是否相交 ####

力扣第 160 题「 [相交链表][Link 4]」

public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode p1 = headA,p2 = headB;
            while (p1!=p2){
                // p1 走一步，如果走到 A 链表末尾，转到 B 链表
                if (p1 == null) p1 = headB;
                else p1 = p1.next;
                // p2 走一步，如果走到 B 链表末尾，转到 A 链表
                if (p2 == null) p2 = headA;
                else p2 = p2.next;
            }
            return p1;
        }
    }

参考学习资料：[双指针技巧秒杀七道链表题目 :: labuladong的算法小抄][_ labuladong 1]

[Link 1]: https://leetcode.cn/problems/merge-two-sorted-lists/
[Link 2]: https://leetcode.cn/problems/partition-list/
[K]: https://leetcode.cn/problems/merge-k-sorted-lists/
[_ labuladong]: https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-daeca/er-cha-dui-1a386/
[PriorityQueue_ poll_-CSDN]: https://blog.csdn.net/weixin_45771158/article/details/126892136
[N]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
[Link 3]: https://leetcode.cn/problems/middle-of-the-linked-list/
[_ labuladong 1]: https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/
[Link 4]: https://leetcode.cn/problems/intersection-of-two-linked-lists/