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

【算法】LeetCode：链表篇_leetcode 链表

作者：知新_RL | 2024-05-24 15:49:31

赞

踩

leetcode 链表

一、理论基础

1.1 概述

什么是链表

  • 链表是一种通过指针串联在一起的线性结构
  • 入口节点称为链表的头结点也就是head。最后一个节点的指针域指向null（空指针的意思）。
public class ListNode {
    // 值
    int val;
    // 指针
    ListNode next;

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

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

单链表

在这里插入图片描述

双向链表

在这里插入图片描述

循环链表

在这里插入图片描述

1.2 存储方式

在这里插入图片描述

1.3 相关操作与性能分析

删除节点

在这里插入图片描述

添加节点

在这里插入图片描述

性能分析

  • 数组长度一旦定义长度固定。
  • 链表的长度不固定。可以动态增删
插入 /删除（时间复杂度）查询（时间复杂度）适用场景
数组O(n)O(1)数据量固定，频繁查询，较少增删
链表O(1)O(n)数据量不固定，频繁增删，较少查询

二、LeetCode题序

  • 虚拟头结点：不然针对头结点的情况都要单独处理
  • 双指针

203 (简单)移除链表元素

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

/**
 * head为链表的第一个结点
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //1.生成待检测结点的前一个结点h，构造while结构
        ListNode h=new ListNode(-1);
        h.next=head;
        //2.用待检测节点的前一个节点去遍历
        ListNode buf=h;
        while(buf.next!=null){
            if(buf.next.val==val){
                buf.next=buf.next.next;
            }else{
                buf=buf.next;
            }
        }
        return h.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; }
 * }
 */

  • 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

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 个节点。
/**
 * head：为空结点，next指向链表的第一个结点
 */
class MyLinkedList {
    int size;
    Node head;

    public MyLinkedList() {
        size=0;
        head=new Node(0);
    }

    public int get(int index) {
        if(index>=size || index<0 || size<=0) return -1;
        Node node=head;
        for(int i=0;i<=index;i++){
            node=node.next;
        }
        return node.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>size) return;
        index=Math.max(0,index);
        size++;	//注意：记得要size++
        Node pres=head;
        for(int i=0;i<index;i++){
            pres=pres.next;
        }
        Node newNode=new Node(val);
        newNode.next=pres.next;
        pres.next=newNode;
    }

    public void deleteAtIndex(int index) {
        if(index>=size || index<0 || size<=0) return;
        size--;
        Node pres=head;
        for(int i=0;i<index;i++){
            pres=pres.next;
        }
        Node node=pres.next;
        pres.next=node.next;
        node.next=null;
    }
}
class Node{
    int val;
    Node next;
    Node(int value){
        this.val=value;
    }
}

  • 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
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61

206 (简单)反转链表

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

/**
 * 方式一：遍历：当反转结点为null时返回前驱节点
 * head：链表的第一个结点
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //1.待反转结点的前结点
        ListNode pre=null;
        //2.待反转结点
        ListNode node=head;
        //3.待反转结点的后结点
        ListNode next=null;
        while(node!=null){
            next=node.next;
            //反转结点
            node.next=pre;
            pre=node;
            node=next;
            if(next!=null) next=next.next;
        }
        return pre;
    }
}
/**
 * 方式二：递归：当反转结点为null时返回前驱节点。
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        return recursive(null,head);
    }
    public ListNode recursive(ListNode before,ListNode head){
        if(head==null) return before;
        ListNode after=head.next;
        head.next=before;
        return recursive(head,after);
    }
}
/**
 * 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; }
 * }
 */

  • 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

24 (中等)两两交换链表中的节点

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

class Solution {
    /**
     * 版本一：虚拟头结点
 	 * 结论：拿到待操作结点的前驱结点：即拿到所有所需结点
 	 */
    public ListNode swapPairs(ListNode head) {
        //1.前驱结点
        ListNode front=new ListNode();
        front.next=head;
        //2.结果结点（虚拟结点）：如果有交换便让front进行操作
        ListNode result=front;
        while(front.next!=null && front.next.next!=null){
            ListNode after=head.next.next;
            front.next=head.next;
            head.next.next=head;
            head.next=after;
            front=head;
            head=head.next;
        }
        return result.next;
    }
    /**
     * 版本二：递归
 	 * 结论：前两个结点指向递归结果
 	 */
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;
        //保存后结点
        ListNode after=head.next.next;
        //保存右结点
        ListNode right=head.next;
        head.next.next=head;
        head.next=swapPairs(after);
        return 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; }
 * }
 */

  • 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

19 (中等)删除链表的倒数第 N 个结点

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

/**
 * 思路：双指针-在确认链表长度的同时确定待删除结点的前驱结点
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //1.待删除结点的前驱结点
        ListNode front=new ListNode();
        front.next=head;
        //2.尾结点
        ListNode tail=front;
        //3.计算结点个数，前驱结点根据该数值移动
        int count=0;
        //4.结果结点
        ListNode result=front;
        while(tail.next!=null){
            count++;
            tail=tail.next;
            if(count>n) front=front.next;
        }
        front.next=front.next.next;
        return result.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; }
 * }
 */

  • 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

面试题 02.07 (简单)链表相交

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

在这里插入图片描述

/**
 * 思路：如果相交，即两链表尾部重合。所以应当从尾部长度相等开始判断是否相同。
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode node=null;
        //计算链表A、链表B的长度
        int lenA=0,lenB=0;
        node=headA;
        while(node!=null){
            lenA++;
            node=node.next;
        }
        node=headB;
        while(node!=null){
            lenB++;
            node=node.next;
        }
        if(lenA==0 || lenB==0) return null;
        //保证A链表为长链表
        if(lenA<lenB){
            node=headA;
            headA=headB;
            headB=node;
            int buf=lenA;
            lenA=lenB;
            lenB=buf;
        }
        for(int i=0;i<lenA-lenB;i++){
            headA=headA.next;
        }
        while(headA!=null){
            if(headA==headB) return headA;
            headA=headA.next;
            headB=headB.next;
        }
        return null;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = 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
  • 49
  • 50

142 (中等)环形链表 II

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

在这里插入图片描述

/**
解题思路：
	1.假设慢指针走过的步数为 x+y ，快指针走过的步数则为 x+y+n(z+y)
	2.当快、慢指针相遇时存在：2(x+y)=x+y+n(z+y)
	3.到入口结点的步数：x+y=n(z+y) --> x=(z+y)(n-1)+z
	所以，当n>=1时：从快、慢指针相遇结点和头结点head开始，每次走一步，两结点相遇的结点即为环形入口结点
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        //1.慢指针
        ListNode slow=head;
        //2.快指针
        ListNode fast=head;
        //3.相遇结点
        ListNode meet=null;
        //4.入口结点
        ListNode entrance=head;
        while(head !=null && fast.next!=null && fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                meet=fast;
                break;
            } 
        }
        if(meet==null) return null;
        while(meet!=head){
            meet=meet.next;
            head=head.next;
        }
        return head;
        //存储走过的结点，判断当前结点是否走过
        // Set<ListNode> set=new HashSet();
        // while(head!=null){
        //     if(!set.contains(head)){
        //          set.add(head);
        //          head=head.next;
        //     }
        //     else return head;
        // }
        // return null;
    }
}
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = 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
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/618101
推荐阅读
相关标签

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

  

闽ICP备14008679号