AI 助理
备案控制台
开发者社区 云计算 文章 正文

LeetCode链表集锦

2023-01-11 183
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本篇文章是博主按照代码随想录的链表部分力扣题的一些见解，有一些自己的想法与代码随想录题解结合，能使这部分题理解的更加透彻。

203.移除链表元素


力扣题目链接


题意：删除链表中等于给定值 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

输出：[]


思路：


微信图片_20230111010009.png

设置虚拟头节点，让del节点从头开始遍历，找到相应定值对应的点后完成删除。

完成删除操作使用双指针的方法，前后两个节点紧挨着一步一步往后走，如果找到对应删除节点就让删除的节点的前一个节点的next域跳两步，最后完成遍历后返回虚拟头节点的next域（这才是新的头节点）


代码：


class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null) {
            return null;
        }
        ListNode dummyNode=new ListNode();
        dummyNode.next=head;
        ListNode ahead=dummyNode;
        ListNode cur=head;
        while(cur!=null) {
            if(cur.val==val) {
                ahead.next=cur.next;
                cur=cur.next;
            }else {
                cur=cur.next;
                ahead=ahead.next;
            }
        }
        return dummyNode.next;
    }
}

707. 设计链表

力扣题目链接


题意：


在链表类中实现这些功能：


get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。


思路：

具体思路在代码注释中体现。


代码：


//定义节点
class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val=val;
    }
}
class MyLinkedList {
    int val;
    Node head;
    public MyLinkedList() {
    }
    //该方法用于返回链表长度
    private int size() {
        int count=0;
        Node cur=head;
        while(cur!=null) {
            count++;
            cur=cur.next;
        }
        return count;
    }
    //get(index)
    public int get(int index) {
    //如果下标不合法返回-1
        if(index<0||index>=size())
            return -1;
        Node cur=this.head;
        int count=0;
        while(count!=index) {
            cur=cur.next;
            count++;
        }
        return cur.val;
    }
    //头插
    public void addAtHead(int val) {
        Node node=new Node(val);
        if(head==null) {
            head=node;
            return;
        }
        node.next=this.head;
        this.head=node;
    }
    //尾插
    public void addAtTail(int val) {
        Node node=new Node(val);
        if(head==null) {
            head=node;
            return;
        }
        Node cur=this.head;
        while(cur.next!=null) {
            cur=cur.next;
        }
        cur.next=node;
    }
    //返回对应下标的前一个节点
    private Node searchIndex(int index) {
        Node cur=this.head;
        int count=0;
        while (count!=index-1) {
            count++;
            cur=cur.next;
        }
        return cur;
    }
    //指定下标插入
    public void addAtIndex(int index, int val) {
      //下标<=0 头插
        if(index<=0) {
            addAtHead(val);
            return;
        }
        //下标等于链表长度 尾插
        if(index==size()) {
            addAtTail(val);
            return;
        }
        //下标大于链表长度 直接返回
        if(index>size())
            return;
        //找到指定下标的前一个节点，插入新的节点
        Node cur=searchIndex(index);
        Node node=new Node(val);
        //新节点后后边节点连接
        node.next=cur.next;
        //前一个节点和新节点连接
        cur.next=node;
    }
    //删除指定位置节点
    public void deleteAtIndex(int index) {
      //不合法直接返回 
        if (index < 0 || index >= size()) {
            return;
        }
        //下标为0删除头节点
        if(index==0) {
            head=head.next;
        }else {
        //其他情况还是找到删除节点的前一个节点，让其next域跳两次完成删除
            Node cur=searchIndex(index);
            cur.next=cur.next.next;
        }
    }
}
/**
 * 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->3->4->5->NULL 输出: 5->4->3->2->1->NULL


思路：


微信图片_20230111010004.png

完成倒置，就需要将每个节点的next域指向前一个节点，但如果发生改变就找不到后一个节点了，所以需要找一个临时节点进行存储，然后再进行修改。


代码：

双指针：


class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null)
        return head;
        //前一个节点
        ListNode prev=null;
        //反转节点
        ListNode cur=head;
        //临时节点，用于存储cur节点的下一个节点
        ListNode curNext=null;
        while(cur!=null) {
          //临时节点先进行存储
            curNext=cur.next;
            //当前节点的next指向前一个节点
            cur.next=prev;
            //前一个节点后移
            prev=cur;
            //当前节点后移
            cur=curNext;
        }
        //最后全部反转完成后，prev节点就是反转后链表的头节点
        return prev;
    }
}


递归：


class Solution {
    public ListNode reverseList(ListNode head) {
      //传递的两个参数就是需要反转的两个节点
        return reverse(null,head);
    }
    private ListNode reverse(ListNode prev,ListNode cur) {
        if(cur==null)
        return prev;
        ListNode curNext=cur.next;
        cur.next=prev;
        prev=cur;
        cur=curNext;
        //完成后移以后递归新的反转节点
        return reverse(prev,cur);
    }
}


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

力扣题目链接

题意：

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

微信图片_20230111010000.png


思路：


微信图片_20230111005957.png

代码：


class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode=new ListNode(0);
        dummyNode.next=head;
        ListNode cur=dummyNode;
        //需要交换这两个节点的顺序，所以这两个节点都不能为空
        while(cur.next!=null&&cur.next.next!=null) {
          //先对这两个节点地址进行存储
            ListNode node1=cur.next;
            ListNode node2=cur.next.next;
            cur.next=node2;
            node1.next=node2.next;
            node2.next=node1;
            //最后把cur节点移到下一次两个交换节点的前一个节点
            cur=node1;
        }
        return dummyNode.next;
    }
}

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

力扣题目链接

题意：

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


微信图片_20230111005954.png


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

输出：[1,2,3,5]


思路：

快慢指针，快指针先走一定步数，然后快慢指针一起走，当快指针走出链表为null时，慢指针走到倒数第n+1个节点的位置，让其next域跳两步完成删除


代码：


class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        ListNode slow=dummy;
        ListNode fast=dummy;
        while(n+1>0) {
            fast=fast.next;
            n--;
        }
        while(fast!=null) {
            slow=slow.next;
            fast=fast.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }
}

面试题 02.07. 链表相交


力扣题目链接

题意：

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


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


微信图片_20230111005951.png

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


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


示例 1：


微信图片_20230111005947.png

示例 2：


微信图片_20230111005943.png

示例 3：


微信图片_20230111005940.png


思路：

先对两个链表都完成一次遍历，计算其链表长度，让长的链表头先走两链表之差步，然后两个指针再一起走，第一次next域相同时就是相交处，如果没有相同一直走到空，说明不相交。


代码：


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int countA=count(headA);
        int countB=count(headB);
        int a=countA-countB;
        ListNode curA=new ListNode(0);
        curA.next=headA;
        ListNode curB=new ListNode(-1);
        curB.next=headB;
        if(a>0) {
            while(a-->0)
            curA=curA.next;
        }else {
            a=-a;
            while(a-->0)
            curB=curB.next;
        }
        while(curA!=null&&curB!=null) {
            if(curA.next==curB.next) {
                return curA.next;
            }
            curA=curA.next;
            curB=curB.next;
        }
        return null;
    }
    private int count(ListNode head) {
        ListNode cur=head;
        int count=0;
        while(cur!=null) {
            count++;
            cur=cur.next;
        }
        return count;
    }
}

142. 环形链表 II

力扣题目链接

题意：

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


为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。


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


微信图片_20230111005936.png

思路：


做这道题需要考虑两个事情：


链表是否有环

环的入口在哪里

1、判断有环


定义快慢指针从链表头开始走，快指针每次走两步，慢指针每次走一步，如果有指针走出去为null则一定无环，如果有环则快慢指针一定会相遇。

为什么如果有环快慢指针一定会相遇呢？

快指针先入环，无论慢指针入环时快指针在环的哪个位置，两者的相对速度差一，快指针每次都会靠近慢指针一步，一定会相遇。


2.寻找环的入口


微信图片_20230111005932.png

快指针是慢指针速度的两倍，所以慢指针走一圈快指针就会走两圈，又因为由1中分析，两者以相对速度为一的速度靠近，则一定不会错过（一定相遇），所以慢指针入环后，走不完第一圈就一定会被快指针赶上（快指针也走不完两圈）。

slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A,由此可以得出两者的路程关系等式。


2*（x+y）=x+y+n(y+z)


又由前边分析得，慢指针走不完一圈会被快指针追上，则快指针也走不完两圈，所以n为1

由此得x=z。

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。


代码：


public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null)
        return null;
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow) {
                fast=head;
                while(fast!=slow) {
                    fast=fast.next;
                    slow=slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}


导图总结

微信图片_20230111005922.png




文章标签：
索引
存储
关键词：
LeetCode链表
链表leetcode
如风暖阳
目录
相关文章
白子寰
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
白子寰
164 1
石小浪♪
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题，即合并两个有序链表的问题。
石小浪♪
206 0
Leetcode第21题(合并两个有序链表)
飞川001
|
8月前
|
算法 Go
【LeetCode 热题100】23：合并 K 个升序链表（详细解析）（Go语言版）
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法：优先队列（最小堆）和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值，；分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码，并对比分析两种方法的适用场景，帮助读者深入理解链表操作与算法设计。
飞川001
314 10
石小浪♪
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法，即如何通过使用三个指针（preNode, curNode, curNextNode）来两两交换链表中的节点，并提供了详细的代码实现。
石小浪♪
156 0
LeetCode第二十四题(两两交换链表中的节点)
石小浪♪
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点，可以通过快慢指针法在一次遍历中实现。
石小浪♪
204 0
Leetcode第十九题(删除链表的倒数第N个节点)
服务端技术栈
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法，通过使用虚拟节点和前驱节点技巧，实现了链表中相邻节点的交换。
服务端技术栈
143 3
LeetCode第24题两两交换链表中的节点
服务端技术栈
|
存储 算法
LeetCode第86题分隔链表
文章介绍了LeetCode第86题"分隔链表"的解法，通过创建两个新链表分别存储小于和大于等于给定值x的节点，然后合并这两个链表来解决问题，提供了一种简单易懂且操作原链表的解决方案。
服务端技术栈
138 2
LeetCode第86题分隔链表
服务端技术栈
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法，使用双指针技术在原链表上原地删除重复元素，提供了一种时间和空间效率都较高的解决方案。
服务端技术栈
190 2
LeetCode第83题删除排序链表中的重复元素
服务端技术栈
|
算法
LeetCode第23题合并 K 个升序链表
这篇文章介绍了LeetCode第23题"合并K个升序链表"的解题方法，使用分而治之的思想，通过递归合并链表的方式解决了这个难题。
服务端技术栈
145 2
LeetCode第23题合并 K 个升序链表
风吹落叶花飘荡
|
C++ 索引
leetcode 707.设计链表
本文提供了解决LeetCode 707题"设计链表"的C++实现，包括单链表的节点定义和类方法实现，如添加节点、获取节点值、删除节点等。
风吹落叶花飘荡
112 1