`
eriol
  • 浏览: 409219 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

单向链表中的一些算法

阅读更多

1. 在一个单向链表中,寻找链表中间节点。

使用两个指针,快指针每次步进为2,慢指针每次步进为1。当快指针到达链表尾部时,慢指针指向的就是链表的中间。

 

Node findMiddleNode(Node head) {
    if (head == null)
        return head;
    
    Node p1 = head;
    Node p2 = p1.next;
  
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;
    }
    return p1;
}

 

2. 在单向链表中寻找倒数第n个元素

思路同1,使用两个指针,它们之间保持n的距离,当第一个指针到达链表尾部时,第二个指针指向的就是链表的倒数第n个元素。

 

Node findLastNNode(Node head, int n) {
    Node p1 = head;
    Node p2 = head;
    
    int i;
    for (i = 0; p1 != null && i < n; i++) {
        p1 = p1.next;
    } 
    if (i != n)
        return null;  // 链表长度小于n
  
    while (p1 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p2;
}

 

3. 判定链表中是否存在环

思路同1,使用两个指针,p1每次步进为2,p2每次步进为1,循环直到p2等于null或者两个指针相等。若p2==null,说明该链表不存在环;若p1==p2,说明存在环。

 

bool isLoop(Node head) {
    if (head == null)
        return false;
    Node p1 = head;
    Node p2 = p1.next;

    while (p2 != null && p2.next != null && p1 != p2) {
        p1 = p1.next;
        p2 = p2.next.next;
    }
    if (p1 == p2) 
        return true;
    else
        return false;
}
0
0
分享到:
评论

相关推荐

    单向链表 代码架构

    单向链表是一种基本的数据结构,它在计算机科学和编程中有着广泛的应用。与数组不同,链表中的元素不是在内存中连续存储的,而是通过指针或引用连接在一起,形成一个逻辑上的线性序列。单向链表的每个节点包含两部分...

    实验二 单向链表的有关操作.cpp

    1.随机产生或键盘输入一组元素,建立一个带头结点的单向链表(无序)。 2.遍历单向链表。 3.把单向链表中元素逆置(不允许申请新的结点空间)...利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。

    单向链表源代码

    单向链表是一种基本的数据结构,它在计算机科学中被广泛应用,特别是在算法和数据结构的实现中。在Java编程中,单向链表通常通过定义一个节点类来实现,每个节点包含数据和指向下一个节点的引用。下面我们将深入探讨...

    C#单向链表的实现

    本文将详细讲解如何在C#中实现单向链表,结合源码解析来帮助你深入理解其内部机制。 首先,我们要知道什么是单向链表。单向链表是由一系列节点组成,每个节点包含两个部分:数据域和指针域。数据域存储实际的数据,...

    04.单向链表以及单向链表的应用.ppt

    04.单向链表以及单向链表的应用.ppt

    数据结构 单向链表 双向链表 源程序

    本文将深入探讨两种重要的线性数据结构——单向链表和双向链表,以及它们在实际编程中的应用。 单向链表是一种线性数据结构,它的每个元素(称为节点)包含两部分:数据域,用于存储实际的数据;指针域,用于存储下...

    链表插入结点算法

    下面给出一个具体的C语言代码示例,演示如何实现单向链表中的节点插入操作: ```c #include #include // 定义链表节点结构体 typedef struct Node { int data; struct Node *next; } Node; // 创建新节点的...

    C语言实现的单向链表和双向链表

    在单向链表中插入节点需要找到合适的位置,并更新`next`指针。例如,在链表末尾添加节点的函数可能如下: ```c void append(Node** head, int value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode-...

    单向链表多种功能实现

    在本文中,我们将深入探讨如何实现单向链表的各种操作,包括建立链表、添加元素、删除元素、翻转链表(包括递归方法)、合并链表、查找链表中的回路以及定位回路的起点。 1. **建立链表** 建立链表通常从创建一个...

    单向链表.cpp 单向链表实现 包括类定义与测试

    单向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 作者Clifford A.Shaffer 重庆大学使用教材

    单向链表实现基排序

    在实际编程中,单向链表实现基排序可能涉及一些额外的细节,如如何高效地创建和操作链表,如何避免溢出问题,以及如何处理负数和不同基数的情况。此外,基数排序的效率受到基数大小的影响,基数越大,排序的效率可能...

    C语言实现单向链表及操作

    数据结构,c语言实现的单向链表。代码分享 struct LinkNode { int data; struct LinkNode *next; }; typedef struct LinkNode *Lnode;

    已知head指向一个带头结点的单向链表

    已知head指向一个带头结点的单向链表, 链表中每个结点包含数据域(data)和指针域(next)。 请编写函数实现如图所示链表逆置

    基于数据结构的单向链表排序算法探究.pdf

    #资源达人分享计划#

    C#泛型实现单向链表实现

    总的来说,C#中的泛型单向链表实现是一个典型的编程实践,它展示了如何利用泛型提高代码的可重用性,同时利用链表的数据结构特性解决特定问题。通过学习和理解这个主题,开发者可以提升对数据结构和C#特性的掌握,这...

    单向链表 操作 经典

    单向链表是一种基本的数据结构,它由一系列节点组成,每个节点包含数据和一个指向下一个节点的指针。在C++或类似编程语言中,处理链表时常常使用指向指针的指针(也称为二级指针),这是因为链表中的元素不是连续...

    单向链表类模板(全)C++

    在C++编程中,单向链表是一种基本的数据结构,用于存储动态集合。单向链表的特点是每个节点包含一个数据元素和一个指向下一个节点的指针,最后一个节点的指针为空。本压缩包文件提供了实现单向链表类模板的完整代码...

    单向链表实现

    单向链表在各种数据结构(如栈、队列、哈希表)以及算法(如LRU缓存淘汰策略)中都有应用。例如,链表可以用来实现动态分配内存的内存池,或者作为操作系统中的进程控制块链表。 总结,单向链表是数据结构的基础,...

    Java算法(链表操作实例)

    4. **反转链表**:这是一个常见的链表算法问题,可以递归或迭代地解决。以下是一个迭代的解决方案: ```java public ListNode reverseList(ListNode head) { ListNode prev = null, current = head, nextTemp = ...

Global site tag (gtag.js) - Google Analytics