刷题笔记(链表)-12

勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

导读:本篇文章讲解 刷题笔记(链表)-12,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

环形链表

题目地址:141. 环形链表 – 力扣(LeetCode) (leetcode-cn.com)

WT8EjK.png

思路:递归

  • 利用Set去重的特点,添加节点,如果节点重复,返回True
  • 递归直到结束
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while(head!=null){
            if (!set.add(head)){
                return true;
            }
            head=head.next;
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度:O(N),其中N是链表中的节点数。最坏情况下我们需要遍历每个节点一次

  • 空间复杂度:O(N),其中N是链表中的节点数。主要为哈希表的开销,最坏情况下我们需要将每个节点插入到哈希表中一次

双指针法

参考官方题解学到了还可以这样解,还了解到有个龟兔赛跑算法😂环形链表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        // 定义快慢指针
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

合并两个有序链表

题目地址:21. 合并两个有序链表 – 力扣(LeetCode) (leetcode-cn.com)
WT3sTH.png

思路

递归

  • 判断链表是否为空,为空就返回另一个链表不做任何操作
  • 否则判断两个链表哪个头节点的值更小,然后递归调用将下一个添加到结果的节点
  • 递归结束条件:任以链表为空,递归结束
/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

复杂度分析

  • 时间复杂度:O(n + m),其中n和m分别为两个链表的长度

  • 空间复杂度:O(n + m),其中n和m分别为两个链表的长度

反转字符串

题目地址:344. 反转字符串 – 力扣(LeetCode) (leetcode-cn.com)

WT2q6f.png

思路:

双指针法

class Solution {
    public void reverseString(char[] s) {
         int len = s.length;
        for (int left = 0, right = len - 1; left < right; left++, right--) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
        }
    }
}

复杂度分析

  • 时间复杂度:O(N),其中 N为字符数组的长度。一共执行了 N/2次的交换。
  • 空间复杂度:O(1)

异或法,学到了,这样更快,评论区大神多多!!!

class Solution {
    public void reverseString(char[] s) {
         int l = 0;
        int r = s.length - 1;
        while (l < r) {
            //构造 a ^ b 的结果,并放在 a 中
            s[l] ^= s[r];
            //将 a ^ b 这一结果再 ^ b ,存入b中,此时 b = a, a = a ^ b
            s[r] ^= s[l];
            //a ^ b 的结果再 ^ a ,存入 a 中,此时 b = a, a = b 完成交换
            s[l] ^= s[r];
            l++;
            r--;
            }
    }
}

代码均由力扣编译器,提交通过,描述编写不当地方还请大家评论区指出💪!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/140705.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!