算法宝典1——Java版本(此系列持续更新,这篇文章有20道)(有题目的跳转链接)(此份宝典包含了链表、栈、队列、二叉树的算法题)(上)

简介: 算法宝典1——Java版本(此系列持续更新,这篇文章有20道)(有题目的跳转链接)(此份宝典包含了链表、栈、队列、二叉树的算法题)

一、链表的算法题(目前10道)

1. 移除链表元素(力扣;思路:前后指针)

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

思路:

代码:

/**
 * 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 prev = head;
        ListNode cur = head.next;
        while(cur != null){
            if(cur.val == val){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                cur = cur.next;
                prev = prev.next;
            }
        }
        //最后处理第一个节点
        if(head.val == val){
            head = head.next;
        }
         return head;
    }
}

运行结果:

时间复杂度和空间复杂度:

(1)时间复杂度:O(N);(2)空间复杂度:O(1)

2. 反转一个单链表 (力扣;思路:头插法)

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

思路:

代码:

/**
 * 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) {
        //特殊情况一:如果链表为空,就不需要返回
        if(head == null){
            return null;
        }
        //特殊情况二:只有一个节点
        if(head.next == null){
            return head;
        }
        ListNode cur = head.next;//把第二个节点地址保存起来
        head.next = null;//到时第一个节点的next肯定为空,在这里就可以提前改了
        //进入循环,开始进行头插法
        while(cur != null){
            ListNode curNext = cur.next;//保存cur指向的节点
            cur.next = head;//将第一个节点的地址赋值给cur.next
            head = cur;
            cur = curNext;
        }
        return head;
    }
}

运行结果:

时间复杂度和空间复杂度:

(1)时间复杂度:O(N);空间复杂度:O(1)

3. 链表的中间结点(力扣;思路:快慢指针)

题目:思路给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

思路:

代码:

/**
 * 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) {
                //特殊情况:如果只有一个结点
        if(head.next == null){
            return head;
        }
        ListNode quick = head;//快指针
        ListNode slow = head;//慢指针
        //有两种条件都成立表示快指针不走了,(1)quick为空 (2)quick.next为空
        while(quick != null && quick.next != null){
            quick = quick.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

运行结果:

时间复杂度和空间复杂度:

(1)时间复杂度:O(N);(2)空间复杂度:O(1)

4. 链表中倒数第k个结点(牛客网;思路:①快慢指针、②倒数第几个与步数的关系)

题目:输入一个链表,输出该链表中倒数第k个结点。

思路:

代码:

思路一:

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        //输入值是否正确的判断
        if(k <= 0 || head == null){
            return null;
        }
        ListNode quick = head;
        ListNode slow = head;
        //先让quick走k - 1步
        while (k - 1 != 0){
            quick = quick.next;
            if(quick == null){
                return null;
            }
            k--;
        }
        //快慢指针一起走
        while(quick.next != null){
            quick = quick.next;
            slow = slow.next;
        }
        return slow;
    }
}

思路二:

public ListNode findKthToTail2(int k) {
        //输入值是否正确的判断
        if(k <= 0 || head == null){
            return null;
        }
        int count = 0;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        int i = count - k;
        cur = head;
        if(i < 0){
            return null;
        }
        while(i > 0){
            cur = cur.next;
            i--;
        }
        return cur;
    }

运行结果:

时间复杂度和空间复杂度:

(1)时间复杂度:O(N);(2)空间复杂度:O(1)

5. 合并两个有序链表(力扣)

题目:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路:

代码:

//合并两个升序链表,有问题
    public ListNode mergeTwoLists(ListNode list1, ListNode list2){
        //处理空表的情况
        if(list1 == null && list2 !=null){
            return list2;
        }else if(list1 != null && list2 == null){
            return list1;
        }else if(list1 == null&&list2 == null){
            return null;
        }
        //创建两个地址引用,指向两个链表的首元素结点
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode cur3 = null;//始终指向新链表的终端结点
        //创建一个newList引用
        ListNode newList = null;
        if (cur1.val <= cur2.val){
            newList = cur1;
            cur1 = cur1.next;
            cur3 = newList;
        }else if(cur1.val >= cur2.val){
            newList = cur2;
            cur2 = cur2.next;
            cur3 = newList;
        }
        //开始比较
        while(cur1 != null && cur2 != null ){
            if(cur1.val <= cur2.val){
                cur3.next = cur1;
                cur3 = cur3.next;
                cur1 = cur1.next;
            }else if(cur1.val > cur2.val){
                cur3.next = cur2;
                cur3 = cur3.next;
                cur2 = cur2.next;
            }
        }
        //当cur1 == null或cur2 == null时,意味着已经到链表的结尾,此时还需要将没有连接上的链表(cur1或cur2)连接接上
        cur3.next = null;
        if(cur1 != null){
            cur3.next = cur1;
        }
        if(cur2 != null){
            cur3.next = cur2;
        }
        return newList;
    }

运行结果:

6. 链表分割(牛客网)

题目:现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

思路:

代码:

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
                // write code here
        //把整个链表看成两部分,创建四个引用来分别指向这两部分
        ListNode bs = null;//小于x部分的起始引用
        ListNode be = null;//小于x部分的终端引用
        ListNode as = null;//大于或等于x部分的起始引用
        ListNode ae = null;//大于或等于x部分的终端引用
        ListNode cur = pHead;
        //开始循环
        while(cur != null){
            //有两种可能性,小于x或者大于等于x
            if(cur.val < x){
                //这部分也有两种情况,①当bs和be都为空,②bs不会空
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null){
                    as = cur;
                    ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //有可能不会同时存在小于x和大于等于x的数据
        if(bs == null){
            return as;
        }
        //特殊情况:如果第一段不为空
        be.next = as;
        //如果第二段为空
        if(as != null){
            ae.next = null;
        }
        return bs;
    }
}

运行结果:

7. 相交链表(力扣)

题目:给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null

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

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

思路:

代码:

public MySinglelist.ListNode getIntersectionNode(MySinglelist.ListNode headA, MySinglelist.ListNode headB) {
        int lenA = 0;//用来记录长度
        int lenB = 0;
        MySinglelist.ListNode pl = headA;
        MySinglelist.ListNode ps = headB;
        //计算pl和ps的链表长度
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        while (ps != null){
            lenB++;
            ps = ps.next;
        }
        //1. len一定是一个正数  2.pl指向的链表一定是最长的  ps 指向的链表一定是最短的
        pl = headA;
        ps = headB;
        //计算彼此之间的差值
        int len = lenA - lenB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //先让长度多的链表先走len步
        while(len != 0){
            pl = pl.next;
            len--;
        }
        //开始找相交的节点
        while(pl != ps){
            ps = ps.next;
            pl = pl.next;
        }
        //pl == ps
       /* if(pl == null) {
            return null;
        }*/
        return pl;
    }

运行结果:

8.  链表的回文结构(牛客网)

题目:对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

思路:

定义快慢指针:

(1)找到中间结点

(2)翻转慢指针到快指针部分的结点

(3)首尾互相判断是否符合回文结构

代码:

public boolean chkPalindrome(ListNode head) {
        if(head == null){
            return false;
        }
        if(head.next == null){
            return true;
        }
        // write code here
        //先定义快慢指针
        ListNode quick = head;
        ListNode slow = head;
        //1. 找中间结点
        while(quick != null && quick.next != null){
            quick = quick.next.next;
            slow = slow.next;
        }
        //2. 翻转
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;//先记录下来后一个结点
            cur.next = slow;//实现翻转
            slow = cur;//保存上一个结点的地址
            cur = curNext;//找到下一个结点
        }
        //3.开始判断
        cur = head;
        while(cur != slow){
            //如果不是不相等,返回false
            if(cur.val != slow.val){
                return false;
            }
            //判断偶数的情况:
            if(cur.next == slow){
                return true;
            }
            cur = cur.next;
            slow = slow.next;
        }
        return true;
    }

运行结果:

9.  环形链表(力扣;思路:快慢指针、数学追击问题)

题目:给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false

思路:

代码:

//判断链表是否有环
    //第一种写法
    public boolean hasCycle() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
    //第二种写法
    public boolean hasCycle2() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast  == null || fast.next == null){
            return false;
        }
        return true;
    }

运行结果:

相关文章
|
1天前
|
算法 Java 索引
【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
11 5
|
1天前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
10 2
|
1天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
9 2
|
4天前
|
搜索推荐 算法 前端开发
计算机Java项目|基于协同过滤算法的体育商品推荐系统
计算机Java项目|基于协同过滤算法的体育商品推荐系统
|
4天前
|
算法 前端开发 Java
探讨Java中递归构建树形结构的算法
探讨Java中递归构建树形结构的算法
5 1
|
1月前
|
存储 算法 Java
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)
52 0
|
存储 算法 Java
数据结构算法学习打卡week2 (Java)
数据结构算法学习打卡week2 (Java)
56 0
|
Rust 算法 安全
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)
给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。 子数组 定义为原数组中的一个连续子序列。 请你返回 arr 中 所有奇数长度子数组的和 。
【算法学习】1588. 所有奇数长度子数组的和(java / c / c++ / python / go / rust)
|
Rust 算法 安全
【算法学习】剑指 Offer II 054. 所有大于等于节点的值之和|538|1038(java / c / c++ / python / go / rust)
给定一个二叉搜索树,请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。 提醒一下,二叉搜索树满足下列约束条件: 节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。
【算法学习】剑指 Offer II 054. 所有大于等于节点的值之和|538|1038(java / c / c++ / python / go / rust)
|
存储 Rust 算法
【算法学习】剑指 Offer II 083. 没有重复元素集合的全排列|46. 全排列(java / c / c++ / python / go / rust)
给定一个不含重复数字的整数数组 nums ,返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
【算法学习】剑指 Offer II 083. 没有重复元素集合的全排列|46. 全排列(java / c / c++ / python / go / rust)