数据结构——算法设计实践

4 mins.4.8k50

线性表

NO.1 链表交叉逆序

从1到n顺序排列的n个元素带头结点单链表L = {a1, a2, …, an}，列表定义为

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode;

请设计一个算法，将L重新排列为L’ = {a1, an, a2, an-1, a3, an-2, …}，即将L的前半部分和后半部分交替排列。

要求：

时间复杂度为O(n)。
空间复杂度为O(1)。

Solution:

将链表分为两部分，前半部分和后半部分，然后将后半部分逆序，再交替合并两个部分。逆序和合并的操作分别时间复杂度为O(n)和O(n)，总时间复杂度为O(n)，原地操作空间复杂度为O(1)。

void Function(LNode *L) {
    // 找到链表中间位置后，将后半部分逆序
    LNode *slow = L->next, *fast = slow;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    LNode *mid = slow->next;
    slow->next = NULL;
    LNode *pre = NULL, *next = NULL;
    while (mid) {
        next = mid->next;
        mid->next = pre;
        pre = mid;
        mid = next;
    }
    mid = pre;

    // 从mid和头结点开始交叉合并两个链表
    pre = L->next;
    while (mid) {
        LNode *q = mid->next;
        mid->next = pre->next;
        pre->next = mid;
        pre = pre->next->next;
        mid = q;
    }
}

NO.2 链表的公共后缀

给定两个单链表L1和L2，要求找出它们的公共后缀部分。即找出从某个结点开始，L1和L2的后续结点完全相同的部分。

要求：

时间复杂度为O(n)。

Solution:
找到链表的公共后缀按理说应该从后向前遍历，但所给单链表无法实现。
由于共同后缀的长度应一样，所以我们可以首先计算链表长度差距，将长链表后半部分与短链表等长的部分一起检查。

LNode* Funciton(LNode *L1, LNode *L2) {
    int m=1, n=1;
    LNode *p = L1, *q = L2;
    while (p->next) {
        m++;
        p = p->next;
    } 
    while (q->next) {
        n++;
        q = q->next;
    }

    if (m > n) {
        for (int i = 0; i < m - n; i++) p = p->next;
    } else {
        for (int i = 0; i < n - m; i++) q = q->next;
    }

    LNode ans;
    while (p) {
        while (p && p->data != q->data) {
        p = p->next;
        q = q->next;
        }
        ans = p;
        while (p && p->data == p->data) {
        p = p->next;
        q = q->next;
        }
    }

    return ans;
}

NO.3 合并循环链表

给定两个循环链表的头结点L1和L2,要求最快速度将它们合并，m和n分别为L1和L2的长度。

要求：

时间复杂度为O(m+n)。

Solution:
将两个循环链表的尾结点指向对方的头结点即可。

void Function(LNode *L1, LNode *L2) {
    if (!L1 || !L2) return;

    LNode *tail1 = L1;
    while (tail1->next != L1) {
        tail1 = tail1->next;
    }
    tail1->next = L2;

    LNode *tail2 = L2;
    while (tail2->next != L2) {
        tail2 = tail2->next;
    }
    tail2->next = L1;
}

NO.4 链表排序

给定一个单链表头结点L，要求将其按升序排序。

要求：

时间复杂度为O(nlogn)。
就地排序，空间复杂度为O(1)。

Solution:
使用归并排序的思想，将链表分为两部分，分别排序后再合并。由于链表的特性，归并排序可以在O(nlogn)时间内完成。

LNode* Merge(LNode *L1, LNode *L2) {
    LNode dummy;
    LNode *tail = &dummy;
    dummy.next = NULL;

    while (L1 && L2) {
        if (L1->data < L2->data) {
            tail->next = L1;
            L1 = L1->next;
        } else {
            tail->next = L2;
            L2 = L2->next;
        }
        tail = tail->next;
    }

    if (L1) tail->next = L1;
    if (L2) tail->next = L2;

    return dummy.next;
}

LNode* Sort(LNode *L) {
    if (!L || !L->next) return L;

    // 使用快慢指针找到中间结点
    LNode *slow = L, *fast = L;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 分割链表
    LNode *mid = slow->next;
    slow->next = NULL;

    // 递归排序两部分
    LNode *left = Sort(L);
    LNode *right = Sort(mid);

    // 合并已排序的两部分
    return Merge(left, right);
}

NO.5 链表的逆向建立（头插法）

从表尾到表头依次输入n个整数，要求逆向建立一个带头结点的单链表。

要求：

时间复杂度为O(n)。

Solution:
可以使用头插法逆向建立链表。每次读取一个新元素，就将其插入到链表的头部。

LNode* CreateList(int n) {
    LNode *head = (LNode*)malloc(sizeof(LNode));
    head->next = NULL;

    for (int i = 0; i < n; i++) {
        int value;
        scanf("%d", &value);
        LNode *newNode = (LNode*)malloc(sizeof(LNode));
        newNode->data = value;
        newNode->next = head->next;
        head->next = newNode;
    }

    return head;
}

NO.6 循环链表的逆置

给定一个循环链表的头结点L，要求将其逆置。

要求：

时间复杂度为O(n)。

Solution:
可以使用双指针法，遍历链表并将每个结点的next指针指向前一个结点，直到遍历完整个链表。

void ReverseCircularList(LNode *L) {
    if (!L || !L->next || L->next == L) return;

    LNode *prev = NULL, *current = L->next, *next = NULL;
    LNode *tail = L; // 用于记录原链表的尾结点

    do {
        next = current->next;
        current->next = prev ? prev : L; // 如果prev为NULL，说明是第一个结点
        prev = current;
        current = next;
    } while (current != L->next);

    // 更新头结点的next指针
    tail->next = prev;
}