devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Leetcode链表刷题集合_leecode链表题

作者：知新_RL | 2024-05-02 10:59:38

赞

踩

leecode链表题

链表

对链表类算法题做个小集合，题解基本来LeetCode题解与labuladong的算法网站，自己加以理解写注释。代码都是测试跑通的。

下面使用的链表结构：

class ListNode{
    public ListNode next;
    public int val;

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

leetcode 141. 判断链表是否有环

判断链表是否有环

使用快慢指针进行求解。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head,slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;

            if(slow == fast) return true;
        }
        return false;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

leetcode 142. 环形链表 II

142. 环形链表 II：判断链表是否有环的同时，返回链表中环的起始位置节点

// leetcode 142 环形链表 II
// 判断链表是否有环的同时，返回链表中环的起始位置节点
public ListNode detectCycle(ListNode head) {
    // 此处若不判断，当链表只有一个节点时（且无环时），会导致下面代码不正确。
    if(head == null || head.next == null){
        return null;
    }

    ListNode fast = head, slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;

        if(fast == slow) break;
    }
    if(fast != slow){
        return null; // 无环
    }
	
    
    slow = head;
    while(fast != slow){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

通过下面两张《labuladong的算法小抄》图可以明白为什么可以找到环的起始位置。

环形链表 II

环形链表 II

寻找无环单链表的中点

/*
寻找无环单链表的中点
快慢指针，一个块一个慢，块的走到头，慢的刚好在中间
如果是奇数：slow 刚好在中间  ceil(n/2)
如果是奇数：slow 刚好在     n/2
*/
public static ListNode findLinkedListMid(ListNode head){
    ListNode fast=head,slow=head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

寻找无环单链表的倒数第k个节点

/*
    寻找无环单链表的倒数第k个节点
思路：
    1. 先让快指针走 k 次
    2. 之后快指针和慢指针一步一步next。
    3. 当快指针到达尾部时，慢指针指向倒数第k个元素。

 */
public static ListNode findLinkedListEndk(ListNode head,int k){
    ListNode fast=head,slow=head;
    while(fast != null && k != 0){
        fast = fast.next;
        k--;
    }
    if(fast == null){
        return slow; // 说明链表的长度 刚好为 k。倒数第k个元素，也就刚好是第一个元素
    }
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

leetcode 19 删除链表的倒数第 n 个结点

leetcode19题 删除链表的倒数第 n 个结点

  • 解法一
/**
* leetcode 19题： 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
* 假设链表有K个节点
* 第一个while循环 n 次，
* 第二个while循环 k-n 次
* 时间复杂度为 n+k-n = k
* @param head
* @param n
* @return
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
    // 链表为空， 或者只有一个元素且删除当前节点的情况。
    if(head == null || (head.next == null && n == 1)) {
        head = null;
        return head;
    }

    ListNode fast = head, slow = head;
    while(fast != null && n != 0){
        fast = fast.next;
        n--;
    }

    // 这个条件成立说明，要删除的倒数第n个节点，就是head节点本身，这里直接返回，可以防止后面的程序空指针。
    if(fast == null){
        return head.next;
    }

    // 加上 fast.next != null 是为了将 slow 定位到倒数第 n+1 位置的节点，这样方便单链表删除倒数第n个节点。
    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }
    // 删除 slow.next（倒数第n个节点）
    slow.next = slow.next.next;
    return head;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 解法二
public static ListNode findLinkedListEndk(ListNode head,int k){
    ListNode fast=head,slow=head;
    while(fast != null && k != 0){
        fast = fast.next;
        k--;
    }
    if(fast == null){
        return slow; // 说明链表的长度 刚好为 k。倒数第k个元素，也就刚好是第一个元素
    }
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

/**
 * leetcode 19题 ：解法二，利用上面定义的 findLinkedListEndk 函数 + 虚拟节点（防止空指针）
 */
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 获取倒数第n+1个节点
    ListNode x = findLinkedListEndk(dummy,n+1);
    x.next = x.next.next;
    return dummy.next;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

leetcode 21 合并两个有序链表

leetcode21: 合并两个有序链表

保证合并后依然是升序的

// leetcode 21 合并两个有序链表, 保证合并后依然是升序的。
public ListNode margeTwoLists(ListNode n1 , ListNode n2){
    if(n1 == null || n2 == null){
        return n1 != null ? n1 : n2;
    }

    ListNode temp = new ListNode(-1);
    ListNode p1 = temp;
    while (n1 != null && n2 != null){
        if (n1.val < n2.val){
            p1.next = n1;
            n1 = n1.next;
        }else {
            p1.next = n2;
            n2 = n2.next;
        }
        p1 = p1.next;
    }

    p1.next = (n1 != null ? n1 : n2);
    return temp.next;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

leetcode 23.合并 k 个有序链表

leetcode23: 合并 k 个有序链表

/**
     * leetcode 23 合并 k 个有序链表
     * @param lists
     * @return
     *
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     * 解释：链表数组如下：
     * [
     *   1->4->5,
     *   1->3->4,
     *   2->6
     * ]
     * 将它们合并到一个有序链表中得到。
     * 1->1->2->3->4->4->5->6
     */
public ListNode mergeKLists(ListNode[] lists) {
    ListNode ans = null;
    // 先写一个合并两个链表的方法， 将两个链表传入，返回合并后的链表 mlist
    // 利用合并后的 mlist 在和 下一个链表, 在进行两个链表的合并。
    // 将问题拆分为多个合并两个链表的问题。
    for (ListNode l:lists) {
        ans = margeTwoLists(ans,l);
    }
    return ans;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

leetcode 23.合并 k 个有序链表(通过优先级队列)

/*
leetcode 23 合并 k 个有序链表。通过优先级队列：最小堆、小根堆实现合并。
 */
public ListNode margeKListsUsingPriorityQueue(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);
    // 将每个链表的第一个结点加入小根堆。那么堆顶的节点就是值最小的
    for (ListNode l:lists) {
        if(l != null)  pq.add(l);
    }
    while(!pq.isEmpty()){
        // 取出堆顶元素
        ListNode minNode = pq.poll();
        // 加入最终链表
        p.next = minNode;

        // 将当前 minNode 的下一个元素加入 小根堆（也就是k个链表中每次取出的最小值节点 minNode 的下一个节点）
        // 这一步为何要添加，可以通过下面的注释理解
        if(minNode.next != null){
            pq.add(minNode.next);
        }
        p = p.next;
    }
    return dummy.next;
}

/*
具体流程：
二维链表：[[1,4,5],[1,3,4],[2,6]]
第一轮循环 pq 中的元素 1 1 2，利用pq的特性取出 1，加入下一个元素 3
第二轮循环 pq 中的元素 3 1 2，利用pq的特性取出 1，加入下一个元素 4
第三轮循环 pq 中的元素 3 4 2，利用pq的特性取出 2，加入下一个元素 6
第四轮循环 pq 中的元素 3 4 6，利用pq的特性取出 3，加入下一个元素 4
第五轮循环 pq 中的元素 4 4 6，利用pq的特性取出 4，加入下一个元素 5
第六轮循环 pq 中的元素 5 4 6，利用pq的特性取出 4，加入下一个元素：null（不做添加）
第七轮循环 pq 中的元素 5 6，  利用pq的特性取出 5，加入下一个元素：null（不做添加）
第八轮循环 pq 中的元素 6，    利用pq的特性取出 6，加入下一个元素：null（不做添加）
*/

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

leetcode 86 题分隔链表

分隔链表

/**
 * leetcode 86题分隔链表：
 * 链表中的一个值。要求使用这个值将链表分成两个链表，
 * 所有小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
 * @param head 单链表
 * @param x 目标值
 * @return
 *
 * 示例：
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 *
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 * 思路：
 * 0. 创建两个链表：A与B
 * 1. A 保存值小于 x 的节点（且不改变相对顺序）
 * 2. B 保存大于等于 x 的节点（且不改变相对顺序）
 * 3. A 的尾部链接上B的头部即可
 */
public ListNode partition(ListNode head, int x) {
    // tempLeft 用于存放小于 x 的节点，tempRIght 用于存放大于 x 的节点
    ListNode tempLeft = new ListNode(-1),tempRight = new ListNode(-1);

    ListNode p1 = tempLeft, p2 = tempRight;
    ListNode p = head;
    while(p != null){
        // 注意：这里不能使用 p.val <= x。只保留小于 x 的。
        if(p.val < x){
            p1.next = p;  // 这里赋值为 p 后面需要断开 p.next.
            p1 = p1.next;
        }else {
            p2.next = p;
            p2 = p2.next;
        }
        ListNode temp = p.next;
        p.next = null;
        p = temp;
    }
    // 用 p1 的尾结点，链接tempRight的首节点
    p1.next = tempRight.next;
//        返回tempLeft首节点即可
    return tempLeft.next;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

Leetcode160 两个链表是否相交

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

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

在这里插入图片描述

解法一：这种解法每次都定位到倒数第k个节点，逐步向前比较，只要节点不相等就返回下一个节点（可能是相交的节点，也可能是null代表两个链表不相交）

时间复杂度：O(n^2)

public static ListNode findLinkedListEndk(ListNode head,int k){
    ListNode fast=head,slow=head;
    while(fast != null && k != 0){
        fast = fast.next;
        k--;
    }
    if(fast == null){
        return slow; // 说明链表的长度 刚好为 k。倒数第k个元素，也就刚好是第一个元素
    }
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

/**
     * Leetcode160 两个链表是否相交
     * @param headA  headB
     */
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int i = 1;
    ListNode dummy01 = new ListNode(-1);
    ListNode dummy02 = new ListNode(-1);
    dummy01.next = headA;
    dummy02.next = headB;

    ListNode temp01 , temp02;
    while(true){
        // 从倒数第一个开始，逐步向前找节点
        temp01 = findLinkedListEndk(dummy01,i);
        temp02 = findLinkedListEndk(dummy02,i);

        // 节点只要有一个为空， 就说明已经遍历完了，两个链表没有交点
        if(temp01 == null || temp02 == null){
            break;
        }

        // 如果节点不相等，那么他们的下一个就是交点。
        if(temp01 != temp02){
            // 如果没有交点，在倒数第一个节点的 next 就为 null，结果依旧是正确的。
            return temp02.next;
        }
        // 用于控制倒数第i个节点的变量
        i++;
    }
    return null;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

解法二：

/**
思路：
比如：list1 ： [1,2, 3, 8, 4, 6]  len1 = 6 
     list2 ： [9,15,	  8, 4, 6]  len2 = 5
二者在8的位置相交
1. 求出len1 与 len2。
2. 	if len1 > len2
		then list1 = list1.next // 执行 len1-len2 步
	if len1 < len2
		then list2 = list2.next // 执行 len2-len1 步
	
	通过上面的两步可以将不同长度的链表指针修改为
	list1 ： [1,2, 3, 8, 4, 6]  list1：从2开始
	list2 ： [  9,15, 8, 4, 6]  list2：从9开始
	这样二者只需要一起next就可以同时到达 8 ，得到节点有交点，如果没有交点，那就是同时到达 null。
	
	if len1 == len2
		then 两个链表的长度一致，
	
	loop list1 != list2
	 	list1 = list1.next; 
	 	list2 = list2.next;
*/
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++;
    }
    // 让较长的链表向前走 |lenA - lenB| 步，与较短的链表到达尾部节点的距离一样长。
    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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

参考

https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/
https://leetcode.cn/problemset/all/

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号