iOS单向链表数据结构

作者: 大雄記 | 来源:发表于2017-04-05 15:48 被阅读431次

算法与数据结构知识汇总（二、链表）
2019-12-04 Java-LinkedList源码解读
用Java写单向链表
算法
数据结构 | 其二链表
iOS 数据结构之链表
线性表-单向循环链表
数据结构笔记
链表反转
总结

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。如下图：

下面处理的全部是单链表
单链表的基本结构：

typedef struct node {
    char *data; 
    struct node *next; 
} node_t;

设定一个打印链表的函数:

void list_display(node_t *head)
{
    for (; head; head = head->next)
        printf("%s ", head->data);
    printf("\n");
}

1.计算一个链表的长度（复杂度O(n)）
算法：定义一个p指针指向头结点，步长为1，遍历链表。

int list_len(node_t *head)
{
    int i; 
    for (i = 0; head; head = head->next, i++); 
    return i; 
}

2.反转链表（复杂度O(n)）
算法：t遍历链表, q记录t的上一个结点, p是一个临时变量用来缓存t的值。

void reverse(node_t *head)
{
    node_t *p = 0, *q = 0, *t = 0; 
    for (t = head; t; p = t, t = t->next, p->next = q, q = p); 
}

3.查找倒数第k个元素（尾结点记为倒数第0个）（复杂度O(n)）
算法：2个指针p, q初始化指向头结点.p先跑到k结点处, 然后q再开始跑, 当p跑到最后跑到尾巴时, q正好到达倒数第k个。

node_t *_kth(node_t *head, int k)
{
    int i = 0; 
    node_t *p = head, *q = head; 
    for (; p && i < k; p = p->next, i++); 
    if (i < k) return 0;
    for (; p->next; p = p->next, q = q->next); 
    return q; 
}

4.查找中间结点（复杂度O(n)）
算法：设两个初始化指向头结点的指针p, q.p每次前进两个结点, q每次前进一个结点, 这样当p到达链表尾巴的时候, q到达了中间。

node_t *middle(node_t *head)
{
    node_t *p, *q; 
    for (p = q = head; p->next; p = p->next, q = q->next){
        p = p->next; 
        if (!(p->next)) break; 
    }
    return q; 
}

5.逆序打印链表（复杂度O(n)）
算法：使用递归（即让系统使用栈）。

void r_display(node_t *t)
{
    if (t){
        r_display(t->next); 
        printf("%s", t->data);
    }
}

6.判断一个链表是否有环（复杂度O(n)）
算法：设两个指针p, q, 初始化指向头.p以步长2的速度向前跑, q的步长是1.这样, 如果链表不存在环, p和q肯定不会相遇.如果存在环, p和q一定会相遇。

int any_ring(node_t *head)
{
    node_t *p, *q; 
    for (p = q = head;p; p = p->next, q = q->next){
        p = p->next; 
        if (!p) break; 
        if (p == q) return 1; //yes
    }
    return 0; //fail find
}

7.找出链表中环的入口结点（复杂度O(n)）
算法：初始化三个指针p，q，r全部指向head，然后p以2的步长行进，q以1的步长行进。当p和q相遇的时候，发出r指针以1的步长行进，当p和r相遇的结点就是环的入口结点。

node_t *find_entry(node_t *head)
{
    node_t *p, *q, *r; 

    for (p = q = head; p; p = p->next, q = q->next){
        p = p->next; 
        if (!p) break; 
        if (p == q) break; 
    }

    if (!p) return 0; //no ring in list

    for (r = head, q = q->next; q != r; r = r->next, q = q->next); 

    return r; 
}

解析:

使用俩指针p和q, p扫描的步长为1, q扫描的步长为2.它们的相遇点为图中meet处(在环上).
假设头指针head到入口点entry之间的距离是K.则当q入环的时候, p已经领先了q为: d = K%n(n为环的周长).
我们设meet处相对entry的距离(沿行进方向)为x, 则有
(n-d)+x = 2x (p行进的路程是q的两倍)
解得x = n-d
那么当p和q在meet处相遇的时候, 从head处再发出一个步长为1的指针r, 可以知道, r和q会在entry处相遇!

8.判断两个链表是否相交（复杂度O(m+n)）
算法：两个指针遍历这两个链表,如果他们的尾结点相同,则必定相交。

int is_intersect(node_t *a, node_t *b)
{
    if (!a || !b) return -1; //a or b is NULL
    for (; a->next; a = a->next); 
    for (; b->next; b = b->next); 
    return a == b?1:0; //return 1 for yes, 0 for no
}

** 9.找两个相交的链表的交点**
算法：p，q分别遍历链表a，b，假设q先到达NULL，此时从a的头结点发出一个指针t，当p到达NULL时，从b的头结点发出s，当s==t的时候即相交。

node_t *intersect_point(node_t *a, node_t *b)
{
    node_t *p, *q, *k, *t, *s; 
    for (p = a, q = b; p && q; p = p->next, q = q->next); 

    k = (p == 0)?q:p; //k record the pointer not NULL
    t = (p == 0)?b:a; //if p arrive at tail first, t = b ; else p = a
    s = (p == 0)?a:b; 
    for (; k; k = k->next, t = t->next); 
    for (; t != s; t = t->next, s = s->next); 
    return t; 
}

10.删除结点d（不给头结点）
算法：把下一个结点e的数据拷贝到d结点的数据区，然后删除e。（缺陷：不能删除尾结点）

node_t *delete(node_t *d) 
{
    node_t *e = d->next; 
    d->data = e->data; 
    d->next = e->next; 
}

11.两个链表右对齐打印
算法：p和q两个指针分别遍历链表a和b，假如q先到达NULL（即a比b长），此时由a头结点发出指针t，打印完整的链表a。同时p继续移动到NULL，并且打印空格。同时还从b头结点发出指针s打印完整的链表b。

void foo(node_t *a, node_t *b)
{
    node_t *p, *q, *k, *t, *s; 
    for (p = a, q = b; p && q; p = p->next, q = q->next); 

    k = p?p:q; 
    t = p?a:b; 
    s = p?b:a; 

    for (; t; printf("%d ", t->data), t = t->next); 
    printf("\n");
    for (; k; printf("  "), k = k->next); 
    for (; s; printf("%d ", s->data), s = s->next); 
}

原文：https://github.com/hit9/oldblog/blob/gh-pages/blog-src/blog/C/posts/25.mkd