专栏首页老沙课堂数据结构与算法(三)链表

数据结构与算法(三)链表

单向链表

单向链表结构如下图所示

单向链表

注意事项

•插入操作的时候 如果想在角标1添加,要找到角标1的上一个元素。•边界问题 例如首个元素添加 以及最后一个元素添加

单向循环链表

单向循环链表

单项循环链表就是在最后一个元素的next 指向第一个元素

注意事项

•单向链表的注意事项 •当元素只有一个的时候,进行删除操作需要注意

双向链表

双向链表

在单链表的基础上 添加一个perv指针,指向上一个元素。用于优化单项链表查找问题。

注意事项

•通常我们添加元素,找到添加元素对应位置的元素 进行插入既可•当添加操作的时候,注意边界问题,特殊处理

双向循环链表

双向循环链表

在双向链表的基础上

将最后一项的next指向首个元素

将第一项的perv的元素指向最后一个元素

注意事项

•删除操作只剩下一个元素的问题•边界处理问题

建议手写代码实现上述操作的增删查改,以及在leet code上刷关于链表的题、

面试题:

1、翻转链表

将一个单链表进行翻转

链表为1,2,3,4,5 翻转输出为5,4,3,2,1

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

123123

//递归
public ListNode reverseList(ListNode head) {
  if (head == null || head.next == null) {
  return head;
}
  ListNode headerListNode = reverseList(head.next);
  head.next.next = head;
  head.next = null;
    return headerListNode;
}

递归思想:

将事件模拟成最小单元事件。以及方法想要做的事情。

//迭代
public ListNode reverseList2(ListNode head) {
  ListNode temp = null;
  ListNode newHeader = null;

  while(head != null) {

    temp = head.next;
    head.next = null;
    newHeader = head;
    head = temp;
  }
    return newHeader;
}

迭代思想

借助新的链表,遍历旧链表,在新的链表上头插法进行插入(在角标为0的位置插入)

时间复杂度

两种方式的时间复杂度都是O(n)

2、判断一个链表是否有环

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;
}

思想

快慢指针方式 例如在赛道上两人跑步,跑的快的是跑的慢的速度的两倍,如果是环形赛道,跑的慢的终究会和跑的快的相遇(跑的路程比你多一圈)。

时间复杂度

时间复杂度都是O(n)

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:沙睿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构与算法(二)数组

    在堆中连续开辟的一段空间,每个元素占有相同大小的空间。一经开辟,即固定大小,无法改变长短。

    老沙
  • iOS读写安全

    给属性添加atomic 可以保证属性的setter和getter原子性操作,也就是保证setter和getter内部是线程同步的

    老沙
  • super(二) 以及内存分布

    在ViewController 书写以下代码。问是否能编译通过,如果可以输出什么是什么?

    老沙
  • 剑指offer 反转链表

    week
  • LeetCode 19. Remove Nth Node From End of List题目分析代码

    样例 给出链表1->2->3->4->5->null和 n = 2. 删除倒数第二个节点之后,这个链表将变成1->2->3->5->null.

    desperate633
  • LintCode 回文链表题目分析代码

    链表由于其特殊的结构,没法像数组那样判断回文,所以比较原始的方法,先找到链表的中间节点,然后将后半部分反转,然后逐个比较即可。 链表中的算法,通常以寻找链表中...

    desperate633
  • 有环链表

    一份执着✘
  • 链表反转的两种实现方法,后一种击败了100%的用户!

    链表反转是一道很基础但又非常热门的算法面试题,它也在《剑指Offer》的第 24 道题出现过,至于它有多热(门)看下面的榜单就知道了。

    Java中文社群-磊哥
  • [算法总结] 一文搞懂面试链表题

    链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。

    尾尾部落
  • LeetCode-19 删除链表中的倒数第N个节点

    今天我们学习第19题删除链表中的倒数第N个节点,这是一道中等题。这个题属于面试中的高频题,一定要能手写出来。下面我们看看这道题的题目描述。

    用户3470542

扫码关注云+社区

领取腾讯云代金券