[数据结构与算法] leetcode链表练习

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode链表练习 -> 正文阅读

[数据结构与算法]leetcode链表练习

LeetCode链表

这里写目录标题

1.移除链表元素

1.1 题目描述

在这里插入图片描述

1.2 迭代(虚拟头解决)

/**
 * 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 removeElements(ListNode head, int val) {

        //使用虚拟头
        ListNode dummyNode=new ListNode(0,head);
        //让一个指针始终指向虚拟头，虚拟头进行迭代
        ListNode l=dummyNode;
        if(dummyNode.next==null){
            return null;
        }
        while(dummyNode.next!=null){
            if(dummyNode.next.val==val){
                dummyNode.next=dummyNode.next.next;
            }else{
                dummyNode=dummyNode.next;
            }
        }
        return l.next;
      
    }
}

1.3 迭代(不使用虚拟头)

/**
 * 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 removeElements(ListNode head, int val) {
            if(head==null){
            return null;
        }
        ListNode l=head;
        while(l.next!=null){
            //如果val和头结点值相同
            if(head.val==val){
                head=head.next;
                l=l.next;
            }else if(l.next.val==val){
                l.next=l.next.next;
            }else{
                l=l.next;
            }
        }
        //不使用虚拟头的方式，如果链表中全部都是val元素，那么这种方式会使最后一个元素没有判断
        //所以最后需要再判断一次
        if(l.val==val){
            return null;
        }else{
            return head;
        }
    }
}

1.4 思考

? 以后只要有链表中头结点被删除的可能，那么直接使用虚拟头的方式，非常好用！

2.反转链表

2.1 题目描述

在这里插入图片描述

2.2 头插法

? 这种解法需要多余的空间，如果题目的空间复杂度为O(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 ListNode reverseList(ListNode head) {
        //头节点
        ListNode node=null;
        while(head!=null){
            //如果为null，则初始化头节点
            if(node==null){
                node=new ListNode(head.val);
            }else{
                ListNode newNode=new ListNode(head.val,node);
                node=newNode;
            }
            head=head.next; 
        }
        return node; 
    }
}

2.3 原地移动法

? 这种方法不需要开辟新的内存空间，适用于要求空间复杂度为O(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 ListNode reverseList(ListNode head) {
    //判断head是否为null
    //判断链表中是否只有一个元素
    if(head==null || head.next==null){
        return head;
    }
    //让l指向第二个元素
    ListNode l=head.next;
    
    //链表不只有一个元素，那么就可以使用通用方法
    //先让head.next=null，因为此时的head是第一个节点，反转之后成为了最后一个节点，所以head.next=null
    head.next=null;
    while(l!=null && l.next!=null){
        //让一个引用指向l的下一个元素，防止下面操作找不到后面的元素
        ListNode newNode=l.next;
        //后一个元素的next指向前一个元素
        l.next=head;
        //前一个引用后移
        head=l;
        //让l找到后面的元素
        l=newNode; 
    }
    //注意：由于while的终止条件使l走到最后一个元素，并没有使其next指向前一个元素，所以这块补充指向
    l.next=head;
    return l;
}
}

3.链表的中间结点

3.1 题目描述

在这里插入图片描述

3.2 快慢指针

? 设置一个快指针和慢指针，快指针一次走两步，慢指针一次走一步。

? 若链表元素为偶数个，当快指针为null时，慢指针所指向的就是最中间元素

? 若链表元素为奇数个，当快指针的next为null时，慢指针所指向的就是最中间元素(中间第二个元素)

/**
* 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) {
    ListNode low=head;
    ListNode fast=head;

    while(fast!=null && fast.next!=null){
        fast=fast.next.next;
        low=low.next;
    }
    return low;
}
}

4.返回倒数第K个结点值

4.1 题目描述

在这里插入图片描述

4.2 快慢指针

? 返回倒数第K个结点，那么就可以先让fast先走K步，然后让low和fast一块走，fast为null的时候就是要返回的那个结点值。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthToLast(ListNode head, int k) {
        //慢指针
        ListNode low=head;
        //快指针
        ListNode fast=head;
        //让快指针先跑，跑K步
        for(int i=0;i<k;i++){
            fast=fast.next;
        }
        //快指针和慢指针一块走，走到最后就是返回的那个结点
        while(fast!=null){
            fast=fast.next;
            low=low.next;
        }
        return low.val;
    }
}

5.环形链表Ⅱ

5.1 题目描述

在这里插入图片描述

5.2 解题思路

在这里插入图片描述

5.3 代码

5.3.1 快慢指针方法

public ListNode detectCycle(ListNode head) {

    //设置快慢指针，慢指针一次走一步，快指针一次走两步
    ListNode slow=head;
    ListNode fast=head;
    //找到快慢指针相交的地方
    while(true){
        if(fast==null || fast.next==null){
            return null;
        }
        slow=slow.next;
        fast=fast.next.next;
        if(slow==fast){
            break;
        }
    }

    //运行到此处已经找到相交点，并且说明有循环链表，接下来使slow=head
    //此时找到的相交点就是进入循环链表的起点
    slow=head;
    while(slow!=fast){
         fast=fast.next;
         slow=slow.next;
    }
    return fast;
}

5.3.2 方法二

public ListNode detectCycle(ListNode head) {
	/*
	思路：创建一个List集合，将链表上所有的结点都先放入List集合中，等到发现有结点已经存在于List集合中时，
    说明这个结点是循环链表的开始之处
    */
    List<ListNode> list=new ArrayList<>();
    ListNode pos=head;

    while(true){
        if(pos==null || pos.next==null){
            return null;
        }
        if(list.contains(pos)){
            return pos;
        }else{
            list.add(pos);
        }
        pos=pos.next;
    }
}

6.环形链表

6.1 题目描述

在这里插入图片描述

6.2 解题思路

? 和第5题一模一样，甚至比第五题还要少一个步骤，只需要判断链表是否有环即可

6.3 代码

6.3.1 快慢指针方法

public boolean hasCycle(ListNode head) {

    //使用快慢指针，如果两个指针相遇，则肯定是有环链表
    ListNode slow=head;
    ListNode fast=head;
    while(true){
        if(fast==null || fast.next==null){
            return false;
        }
        slow=slow.next;
        fast=fast.next.next;
        if(slow==fast){
            return true;
        }
    }
}

6.3.2 方法二

public boolean hasCycle(ListNode head) {

    //使用List集合将全部结点装进去
    List<ListNode> list=new ArrayList<>();
    ListNode pos=head;
    while(true){
        if(pos==null || pos.next==null){
            return false;
        }
        if(list.contains(pos)){
            return true;
        }else{
            list.add(pos);
        }
        pos=pos.next;
    }
}

7.相交链表

7.1 题目描述

在这里插入图片描述

7.2 解题思路

? 要比较两个链表是否有相交部分时，那肯定是在两个链表长度相同条件下进行比较的，所以
在这里插入图片描述

7.3 代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA==null || headB==null){
        return null;
    }
    ListNode posA=headA;
    ListNode posB=headB;
    while(posA!=posB){
        posA=(posA==null?headB:posA.next);
        posB=(posB==null?headA:posB.next);
    }
    return posA;
}

8.回文链表

8.1 题目描述

在这里插入图片描述

8.2 解题思路

使用快慢指针找到链表的中间元素，要注意偶数个和奇数
将起始元素到中间元素的所有元素存放在栈中，用于与后面的元素进行比对
根据链表的个数进行比对

8.3 代码

public boolean isPalindrome(ListNode head) {
    //如果链表为空或者只有一个元素，那么为true
    if(head==null || head.next==null){
        return true;
    }

    //如果链表结点只有两个，直接进行判断
    if(head.next.next==null){
        if(head.val==head.next.val){
            return true;
        }else{
            return false;
        }
    }

    //快慢指针找到中间元素
    ListNode slow=head;
    ListNode fast=head;
    //设置num初始值为0，目的是防止当链表数只有两个的时候不会被赋值
    int num=0;
    //将中间元素之前的所有元素放入栈中，方便与后面的所有元素进行比对
    Stack stack=new Stack();

    //找最中间的元素，slow将会指向最中间的元素
    while(true){
        stack.push(slow.val);
        //链表数为奇数个
        if(fast.next==null){
            //奇数个元素为1
            num=1;
            break;
        }
        //链表数为偶数个
        if(fast.next.next==null){
            //偶数个元素为0
            num=0;
            break;
        }
        slow=slow.next;
        fast=fast.next.next;
    }


    //链表个数为奇数
    if(num==1){
        stack.pop();
        slow=slow.next;
        while(slow!=null){
            if((int)stack.pop()!=slow.val){
                return false;
            }
            slow=slow.next;
        }
        return true;
    }else{
        //链表个数为偶数;
        slow=slow.next;
        while(slow!=null){
            if((int)stack.pop()!=slow.val){
                return false;
            }
            slow=slow.next;
        }
        return true;
    }
}

9.分割链表

9.1 题目描述

在这里插入图片描述

9.2 解题思路

? 这道题的描述和示例结果不清楚，实际就是将大于等于x的结点全部放在小于结点的后面，结果不唯一

9.3 代码

public ListNode partition(ListNode head, int x) {
    if(head==null){
        return null;
    }

    //虚拟头结点
    ListNode dummyNode1=new ListNode(0);
    dummyNode1.next=head;
    ListNode pos1=dummyNode1.next;
    //新链表
    ListNode dummyNode2=new ListNode();
    dummyNode2.next=null;
    ListNode pos2=dummyNode2;

    //将小于x的结点加入新链表的前面
    while(pos1!=null){
        if(pos1.val<x){
            //添加至新链表
            pos2.next=new ListNode(pos1.val);
            pos2=pos2.next;
            pos2.next=null;
        }
        pos1=pos1.next;
    }

    //将大于等于x的结点加入链表的后面
    pos1=dummyNode1.next;
    while(pos1!=null){
        if(pos1.val>=x){
            pos2.next=new ListNode(pos1.val);
            pos2=pos2.next;
            pos2.next=null;
        }
        pos1=pos1.next;
    }

    return dummyNode2.next;
}

10.合并两个有序链表

10.1 题目描述

在这里插入图片描述

10.2 解题思路

先创建一个链表pos
判断两个链表中最小的结点，连接到pos上，然后将最小的结点所在list=list.next
到最后，肯定有一个list会先为null，那么直接让pos.next=另外一个list

10.3 代码

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

    //虚拟头结点
    ListNode dummyNode=new ListNode();
    dummyNode.next=null;
    ListNode pos=dummyNode;

    ListNode pos1=list1;
    ListNode pos2=list2;

    while(true){
        //如果有某一个链表遍历完了，那么另外一个链表剩余的结点都比这些大，直接连接在后面就行
        if(pos1==null){
            pos.next=pos2;
            break;
        }
        else if(pos2==null){
            pos.next=pos1;
            break;
        }

        //判断哪个链表的结点大
        if(pos1.val<=pos2.val){
            pos.next=new ListNode(pos1.val,null);
            pos=pos.next;
            pos1=pos1.next;
        }else{
            pos.next=new ListNode(pos2.val,null);
            pos=pos.next;
            pos2=pos2.next;
        }
    }

    return dummyNode.next;
}