概述

这是2022版王道数据结构的第2章——线性表的算法大题的C语言代码实现，主要分为顺序表和链表两部分。代码都经过了简单的测试，基本上不会有太大问题，除了对于某些问题可能没有办法完全释放掉链表的内存（例如两个链表有公共部分），造成了一定的内存泄漏。

编译环境为gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0，文件目录结构如下：

└── ch2
    ├── 2-2-sqList.c
    ├── 2-3-linkList.c
    ├── linkList_test.c
    └── sqList_test.c

顺序表

代码实现

#define MAXLISTSIZE 64
typedef int ElementType;
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
    ElementType data[MAXLISTSIZE];
    int length;
} sqList;

//删除顺序表中最小的元素（唯一），空位由最后一个元素填补
bool deleteMin(sqList* L, ElementType* result) {
    if (L->length == 0)
        return false;
    ElementType minElem = L->data[0];
    int minPos = 0;
    int i = 1;
    for (i = 1; i < L->length; ++i) {
        if (L->data[i] < minElem) {
            minElem = L->data[i];
            minPos = i;
        }
    }
    L->data[minPos] = L->data[L->length - 1];
    L->length--;
    *result = minElem;
    return true;
}

//逆转顺序表
void reverse_sqList(sqList* L) {
    ElementType t = 0;
    for (int i = 0, j = L->length - 1; i < j; ++i, --j) {
        t = L->data[i];
        L->data[i] = L->data[j];
        L->data[j] = t;
    }
    return;
}

//删除顺序表中所有=x的元素
void deleteAllX(sqList* l, ElementType x) {
    int k = 0;
    for (int i = 0; i < l->length; ++i) {
        if (l->data[i] != x) {
            l->data[k] = l->data[i];
            k++;
        }
    }
    l->length = k;
}

//删除有序顺序表中所有值在(s,t)之间的元素
bool deleteBetweenS2T_inOrderedSqList(sqList* l, ElementType s, ElementType t) {
    if (l->length == 0 || s >= t)
        return false;
    int i, j;
    for (i = 0; i < l->length && l->data[i] < s; ++i)
        ;
    if (i >= l->length)
        return false;
    for (j = i; j < l->length && l->data[j] <= t; ++j)
        ;

    while (j < l->length) {
        l->data[i] = l->data[j];
        i++;
        j++;
    }
    l->length = i;
    return true;
}

//删除顺序表中所有值在(s,t)之间的元素
bool deleteBetweenS2T_inSqList(sqList* l, ElementType s, ElementType t) {
    int k = 0;
    if (l->length == 0 || s >= t)
        return false;
    for (int i = 0; i < l->length; ++i) {
        if (l->data[i] >= s && l->data[i] <= t) {
            k++;
        } else {
            l->data[i - k] = l->data[i];
        }
    }
    l->length -= k;
    return true;
}

bool deduplicate_inOrderedSqList(sqList* l) {
    if (l->length == 0)
        return false;
    int i = 0;
    for (int j = 1; j < l->length; ++j) {
        if (l->data[i] != l->data[j]) {
            l->data[++i] = l->data[j];
        }
    }
    l->length = i + 1;
    return true;
}

bool merge(sqList* l1, sqList* l2, sqList* l3) {
    if (l1->length + l2->length > MAXLISTSIZE)
        return false;
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < l1->length && j < l2->length) {
        if (l1->data[i] <= l2->data[j]) {
            l3->data[k++] = l1->data[i++];
        } else {
            l3->data[k++] = l2->data[j++];
        }
    }
    while (i < l1->length) {
        l3->data[k++] = l1->data[i++];
    }
    while (j < l2->length) {
        l3->data[k++] = l2->data[j++];
    }
    l3->length = k;
    return true;
}

void reverse_left2right(ElementType* A, int left, int right, int arraySize) {
    if (left >= right || right >= arraySize)
        return;
    int mid = (left + right) / 2;
    ElementType t;
    for (int i = 0; i <= mid - left; ++i) {
        t = A[left + i];
        A[left + i] = A[right - i];
        A[right - i] = t;
    }
    return;
}

void exchange(sqList* l, int m, int n) {
    reverse_left2right(l->data, 0, m + n - 1, l->length);
    reverse_left2right(l->data, 0, n - 1, l->length);
    reverse_left2right(l->data, n, m + n - 1, l->length);
}

void searchExchangeInsert(ElementType* A, int N, ElementType x) {
    int high = N - 1;
    int low = 0;
    int mid;
    while (low <= high) {
        mid = (high + low) / 2;
        if (A[mid] < x) {
            low = mid + 1;
        } else if (A[mid] > x) {
            high = mid - 1;
        } else {
            break;
        }
    }
    if (A[mid] == x && mid != (N - 1)) {
        int t = A[mid + 1];
        A[mid + 1] = A[mid];
        A[mid] = t;
    }
    if (low > high) {
        int i = N - 1;
        for (i = N - 1; i > high; --i) {
            A[i + 1] = A[i];
        }
        A[i + 1] = x;
    }
}

//2010年真题
void reverse(int* A, int left, int right) {
    for (int i = left, j = right; i < j; ++i, --j) {
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
}
void converse(int* A, int N, int p) {
    reverse(A, 0, p - 1);
    reverse(A, p, N - 1);
    reverse(A, 0, N - 1);
}

//2011年真题
int searchMedianInTwoArray(int* A, int* B, int N) {
    int s1 = 0;
    int d1 = N - 1;
    int m1;
    int s2 = 0;
    int d2 = N - 1;
    int m2;
    //当两者都只有一个元素时退出循环
    while (!((s1 == d1) && (s2 == d2))) {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == B[m2]) {
            return A[m1];
        } else if (A[m1] < B[m2]) {
            if ((s1 + d1) % 2 == 0) {
                s1 = m1;
                d2 = m2;
            } else {
                s1 = m1 + 1;
                d2 = m2;
            }
        } else {
            if ((s2 + d2) % 2 == 0) {
                s2 = m2;
                d1 = m1;
            } else {
                s2 = m2 + 1;
                d1 = m1;
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];
}

//2013年真题
int majority(int* A, int N) {
    int m = A[0];
    int count = 1;
    for (int i = 0; i < N; ++i) {
        if (A[i] == m) {
            count++;
        } else {
            if (count > 0) {
                count--;
            } else {
                m = A[i];
                count = 1;
            }
        }
    }
    count = 0;
    for (int i = 0; i < N; ++i) {
        if (A[i] == m)
            count++;
    }
    return count > N / 2 ? m : -1;
}

//2018年真题
int findMissMin(int* A, int N) {
    int i = 0;
    int* B = (int*)malloc(sizeof(int) * (N + 1));
    memset(B, 0, sizeof(int) * (N + 1));
    //B[0]丢弃
    B[0] = -1;
    for (i = 0; i < N; ++i) {
        if (A[i] > 0 && A[i] <= N)
            B[A[i]] = 1;
    }
    for (i = 1; i < N + 1; ++i) {
        if (B[i] == 0)
            break;
    }
    return i;
}

//2020年真题
//这当然不是最优解法，有时候暴力算法也需要练习一下，反正也不指望考试时写出最优算法
int abs(int a) {
    return a < 0 ? -a : a;
}

int findMinDistanceOfTriplet(int* A, int Na, int* B, int Nb, int* C, int Nc) {
    int minDistance = INT_MAX;
    int dis = 0;
    for (int i = 0; i < Na; ++i) {
        for (int j = 0; j < Nb; ++j) {
            for (int k = 0; k < Nc; ++k) {
                dis = abs(A[i] - B[j]) + abs(A[i] - C[k]) + abs(B[j] - C[k]);
                if (dis < minDistance)
                    minDistance = dis;
            }
        }
    }
    return minDistance;
}

测试代码

#include <stdio.h>
#include <stdlib.h>

#include "2-2-sqList.c"

void print_sqList(sqList* l) {
    printf("\nprint_sqList:\n");
    for (int i = 0; i < l->length; ++i)
        printf("%2d ", l->data[i]);
    printf("\n");
}

void init_sqList_randomly(sqList* l, int listLength) {
    if (listLength <= 0 || listLength > MAXLISTSIZE)
        return;
    l->length = listLength;
    for (int i = 0; i < 16; ++i)
        l->data[i] = rand() % (listLength * 2);
}

void print_array(int* a, int n) {
    printf("\n%s:\n", __func__);
    for (int i = 0; i < n; ++i)
        printf("%2d ", a[i]);
    printf("\n");
}

/*test*/

void test_deleteMin() {
    printf("\n%s:\n", __func__);
    sqList l;
    ElementType result;

    init_sqList_randomly(&l, 16);
    print_sqList(&l);
    deleteMin(&l, &result);
    printf("\nresult:%d\n", result);
    print_sqList(&l);
}

void test_reverse_sqList() {
    printf("\n%s:\n", __func__);
    sqList l;

    init_sqList_randomly(&l, 16);
    print_sqList(&l);
    reverse_sqList(&l);
    print_sqList(&l);
}

void test_deleteAllX() {
    printf("\n%s:\n", __func__);
    sqList l;
    init_sqList_randomly(&l, 16);
    l.data[3] = 5;
    l.data[5] = 5;
    l.data[15] = 5;
    print_sqList(&l);

    deleteAllX(&l, 5);
    print_sqList(&l);
}

void test_deleteBetweenS2T_inOrderedSqList() {
    printf("\n%s:\n", __func__);
    sqList l;
    l.length = 16;
    for (int i = 0; i < 16; ++i)
        l.data[i] = 2 * i * i - 13;
    print_sqList(&l);
    deleteBetweenS2T_inOrderedSqList(&l, 5, 65);
    print_sqList(&l);
}

void test_deleteBetweenS2T_inSqList() {
    printf("\n%s:\n", __func__);
    sqList l;

    init_sqList_randomly(&l, 16);
    print_sqList(&l);
    deleteBetweenS2T_inSqList(&l, 4, 12);
    print_sqList(&l);
}

void test_deduplicate_inOrderedSqList() {
    printf("\n%s:\n", __func__);
    sqList l;

    l.data[0] = 1;
    l.data[1] = 2;
    l.data[2] = 3;
    l.data[3] = 3;
    l.data[4] = 5;
    l.data[5] = 8;
    l.data[6] = 8;
    l.data[7] = 8;
    l.data[8] = 9;
    l.length = 9;
    print_sqList(&l);
    deduplicate_inOrderedSqList(&l);
    print_sqList(&l);
}

void test_merge() {
    printf("\n%s:\n", __func__);
    sqList l1;
    l1.length = 8;
    for (int i = 0; i < l1.length; ++i) {
        l1.data[i] = 2 * i + 1;
    }
    sqList l2;
    l2.length = 7;
    for (int i = 0; i < l2.length; ++i) {
        l2.data[i] = i * 2;
    }
    sqList l3;

    merge(&l1, &l2, &l3);
    print_sqList(&l1);
    print_sqList(&l2);
    print_sqList(&l3);
}

void test_exchange() {
    printf("\n%s:\n", __func__);
    sqList l1;
    int i = 0;
    for (i = 0; i < 5; ++i) {
        l1.data[i] = 2 * i + 1;
    }
    for (; i < 12; ++i) {
        l1.data[i] = 2 * (i - 5);
    }
    l1.length = 12;
    print_sqList(&l1);
    exchange(&l1, 5, 7);
    print_sqList(&l1);
}

void test_searchExchangeInsert() {
    printf("\n%s:\n", __func__);
    ElementType a[8];
    a[0] = 1;
    a[1] = 2;
    a[2] = 3;
    a[3] = 6;
    a[4] = 8;
    a[5] = 9;
    a[6] = 10;
    for (int i = 0; i < 7; ++i)
        printf("%3d ", a[i]);
    printf("\n");

    searchExchangeInsert(a, 7, 2);
    for (int i = 0; i < 7; ++i)
        printf("%3d ", a[i]);
    printf("\n");

    a[1] = 2;
    a[2] = 3;
    for (int i = 0; i < 7; ++i)
        printf("%3d ", a[i]);
    printf("\n");
    searchExchangeInsert(a, 7, 7);
    for (int i = 0; i < 8; ++i)
        printf("%3d ", a[i]);
    printf("\n");
}

void test_converse() {
    printf("\n%s:\n", __func__);
    int A[7];
    for (int i = 0; i < 7; ++i)
        A[i] = i + 1;
    for (int i = 0; i < 7; ++i)
        printf("%2d ", A[i]);
    printf("\n");
    converse(A, 7, 4);
    for (int i = 0; i < 7; ++i)
        printf("%2d ", A[i]);
    printf("\n");
}

void test_searchMedianInTwoArray() {
    printf("\n%s:\n", __func__);
    int a[5];
    int b[5];
    for (int i = 5; i < 10; ++i)
        a[i - 5] = 2 * i + 1;
    for (int i = 1; i <= 4; ++i)
        b[i] = 2 * i;
    b[4] = 20;
    print_array(a, 5);
    print_array(b, 5);
    printf("median:%d\n", searchMedianInTwoArray(a, b, 5));
}

void test_majority() {
    printf("\n%s:\n", __func__);
    int A[8];
    A[0] = 0;
    A[1] = 5;
    A[2] = 5;
    A[3] = 3;
    A[4] = 5;
    A[5] = 7;
    A[6] = 5;
    A[7] = 5;
    print_array(A, 8);
    printf("majoriry:%d\n", majority(A, 8));
}

void test_findMissMin() {
    printf("\n%s:\n", __func__);
    int a1[4] = {-5, 3, 2, 3};
    int a2[5] = {1, 2, 3, 4, 5};
    int a3[4] = {1, 2, 4, 5};
    int a4[4] = {3, 5, 6, 2};
    print_array(a1, 4);
    print_array(a2, 5);
    print_array(a3, 4);
    print_array(a4, 4);
    printf("a1:%d\n", findMissMin(a1, 4));
    printf("a2:%d\n", findMissMin(a2, 5));
    printf("a3:%d\n", findMissMin(a3, 4));
    printf("a4:%d\n", findMissMin(a4, 4));
}

void test_findMinDistanceOfTriplet() {
    printf("\n%s:\n", __func__);
    int A[3] = {-1, 0, 9};
    int B[4] = {-25, -10, 10, 11};
    int C[5] = {2, 9, 17, 30, 41};
    printf("minDistance:%d\n", findMinDistanceOfTriplet(A, 3, B, 4, C, 5));
}

int main(int argc, char* argv[]) {
    //test_deleteMin();
    //test_reverse_sqList();
    //test_deleteAllX();
    //test_deleteBetweenS2T_inOrderedSqList();
    //test_deleteBetweenS2T_inSqList();
    //test_deduplicate_inOrderedSqList();
    //test_merge();
    //test_exchange();
    //test_searchExchangeInsert();
    //test_converse();
    //test_searchMedianInTwoArray();
    //test_majority();
    //test_findMissMin();
    test_findMinDistanceOfTriplet();
    return 0;
}

链表

代码实现

typedef int ElementType;
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

struct LNode {
    ElementType data;
    struct LNode* next;
};
typedef struct LNode* LinkList;
typedef struct LNode* PtrToLNode;

//双链表节点
struct DNode {
    ElementType data;
    //这是第20题要用的访问频度域
    int freq;
    struct DNode* prior;
    struct DNode* next;
};
typedef struct DNode* DLinkList;

void deleteX_recursively(LinkList* l, ElementType x) {
    if ((*l) == NULL)
        return;
    if ((*l)->data == x) {
        PtrToLNode p = (*l);
        (*l) = (*l)->next;
        free(p);
        deleteX_recursively(l, x);
    } else {
        deleteX_recursively(&(*l)->next, x);
    }
    return;
}

void deleteX_linkListWithHead(LinkList l, ElementType x) {
    PtrToLNode p = l->next;
    PtrToLNode pre = l;
    while (p != NULL) {
        if (p->data == x) {
            PtrToLNode del = p;
            pre->next = p->next;
            //pre = p;
            p = p->next;
            free(del);
        } else {
            pre = p;
            p = p->next;
        }
    }
}

//递归主体
void printList_inversely_core(LinkList l) {
    if (l->next != NULL)
        printList_inversely_core(l->next);
    if (l != NULL)
        printf("%2d ", l->data);
}

//头结点需要处理一下
void printList_inversely(LinkList l) {
    if (l->next != NULL)
        printList_inversely_core(l->next);
}

//删除链表中的最小元素
LinkList deleteMin(LinkList l) {
    PtrToLNode minPos = l->next;
    PtrToLNode minPrevPos = l;
    PtrToLNode p = l->next;
    PtrToLNode prev = l;
    while (p != NULL) {
        if (p->data < minPos->data) {
            minPos = p;
            minPrevPos = prev;
        }
        prev = p;
        p = p->next;
    }
    minPrevPos->next = minPos->next;
    free(minPos);
    return l;
}

//逆转一个带头结点的单链表
LinkList reverseLinkList(LinkList l) {
    PtrToLNode p = l->next;
    PtrToLNode r;
    l->next = NULL;
    while (p != NULL) {
        r = p->next;
        p->next = l->next;
        l->next = p;
        p = r;
    }
    return l;
}

//对一个带头结点的单链表进行插入和排序
void InsertionSort(LinkList l) {
    if (l == NULL || l->next == NULL || l->next->next == NULL)
        return;
    PtrToLNode p = l->next;
    l->next = NULL;
    PtrToLNode r;

    PtrToLNode tPrev;
    PtrToLNode t;

    while (p != NULL) {
        r = p->next;
        t = l->next;
        tPrev = l;
        while (t != NULL && p->data > t->data) {
            tPrev = t;
            t = t->next;
        }
        p->next = t;
        tPrev->next = p;
        p = r;
    }
}

//删除带头结点的单链表的(min,max)之间的元素
void rangeDelete(LinkList l, int min, int max) {
    PtrToLNode prev = l;
    PtrToLNode p = l->next;
    while (p != NULL) {
        if (p->data > min && p->data < max) {
            PtrToLNode t = p;
            prev->next = p->next;
            p = p->next;
            free(t);
        } else {
            prev = p;
            p = p->next;
        }
    }
}

int linkListLength(LinkList l) {
    PtrToLNode p = l;
    int count = 0;
    while (p != NULL) {
        p = p->next;
        count++;
    }
    return count;
}

PtrToLNode searchFirstCommon(LinkList l1, LinkList l2) {
    int length1 = linkListLength(l1);
    int length2 = linkListLength(l2);
    LinkList longList, shortList;
    int dist = 0;
    if (length1 > length2) {
        longList = l1->next;
        shortList = l2->next;
        dist = length1 - length2;
    } else {
        longList = l2->next;
        shortList = l1->next;
        dist = length2 - length1;
    }
    while (dist--) {
        longList = longList->next;
    }
    while (longList != NULL) {
        if (longList == shortList) {
            return longList;
        } else {
            longList = longList->next;
            shortList = shortList->next;
        }
    }
    return NULL;
}

//每次找到一个最小的元素将其值打印输出并删除该节点
void findMinAndDelete(LinkList l) {
    //prev指向最小元素的前驱
    PtrToLNode prev;
    PtrToLNode p;
    PtrToLNode t;
    //循环到只剩头结点
    while (l->next != NULL) {
        prev = l;
        p = l->next;
        while (p->next != NULL) {
            if (p->next->data < prev->next->data)
                prev = p;
            p = p->next;
        }
        printf("%2d ", prev->next->data);
        t = prev->next;
        prev->next = prev->next->next;
        free(t);
    }
    free(l);
}

//将一个带头结点的单链表按奇偶位置拆分成两个单链表
LinkList splitLinkList(LinkList la) {
    int count = 0;
    LinkList lb = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode p = la->next;
    PtrToLNode rearA = la, rearB = lb;
    la->next = NULL;
    lb->next = NULL;
    while (p != NULL) {
        ++count;
        if ((count & 1) == 0) {
            rearB->next = p;
            rearB = rearB->next;
        } else {
            rearA->next = p;
            rearA = rearA->next;
        }
        p = p->next;
    }
    rearA->next = NULL;
    rearB->next = NULL;

    return lb;
}

//要求与上题相同，但要求lb逆序：采用头插即可
LinkList splitLinkList_2(LinkList la) {
    int count = 0;
    LinkList lb = (LinkList)malloc(sizeof(struct LNode));
    PtrToLNode p = la->next;
    PtrToLNode rearA = la;
    PtrToLNode pSucc;
    lb->next = NULL;
    while (p != NULL) {
        ++count;
        if ((count & 1) == 1) {
            rearA->next = p;
            rearA = rearA->next;
            p = p->next;
        } else {
            pSucc = p->next;
            p->next = lb->next;
            lb->next = p;
            p = pSucc;
        }
    }
    rearA->next = NULL;
    return lb;
}

//删除递增单链表中的重复元素
void deduplicateInOrderedList(LinkList l) {
    if (l == NULL || l->next == NULL || l->next->next == NULL)
        return;
    PtrToLNode rear = l->next;
    PtrToLNode p = rear->next;
    while (p != NULL) {
        if (p->data == rear->data) {
            PtrToLNode succ = p->next;
            rear->next = succ;
            free(p);
            p = succ;
        } else {
            rear = p;
            p = p->next;
        }
    }
}

//将两个递增有序的单链表合并为一个递减有序的单链表
void mergeList(LinkList la, LinkList lb) {
    if (la == NULL && lb == NULL)
        return;
    PtrToLNode pa = la->next;
    PtrToLNode pb = lb->next;
    la->next = NULL;
    free(lb);
    PtrToLNode qa, qb;
    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {
            qa = pa->next;
            pa->next = la->next;
            la->next = pa;
            pa = qa;
        } else {
            qb = pb->next;
            pb->next = la->next;
            la->next = pb;
            pb = qb;
        }
    }
    //统一处理pb
    if (pa != NULL)
        pb = pa;
    while (pb != NULL) {
        qb = pb->next;
        pb->next = la->next;
        la->next = pb;
        pb = qb;
    }
}

//求两个递增链表中的公共元素
LinkList getCommon(LinkList la, LinkList lb) {
    if (la == NULL || lb == NULL)
        return NULL;
    LinkList lc = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode rearC = lc;
    PtrToLNode pa = la->next;
    PtrToLNode pb = lb->next;
    while (pa != NULL && pb != NULL) {
        if (pa->data == pb->data) {
            PtrToLNode new = (PtrToLNode)malloc(sizeof(struct LNode));
            new->data = pa->data;
            rearC->next = new;
            rearC = rearC->next;
            pa = pa->next;
            pb = pb->next;
        } else if (pa->data < pb->data) {
            pa = pa->next;
        } else {
            pb = pb->next;
        }
    }
    rearC->next = NULL;
    return lc;
}

//求la和lb的交集，结果存放于la中
void intersection(LinkList la, LinkList lb) {
    if (la == NULL || lb == NULL || la->next == NULL || lb->next == NULL)
        return;
    PtrToLNode pa = la->next;
    PtrToLNode pb = lb->next;
    PtrToLNode rear = la;
    la->next = NULL;
    free(lb);

    PtrToLNode t;
    while (pa != NULL && pb != NULL) {
        if (pa->data == pb->data) {
            rear->next = pa;
            rear = rear->next;
            pa = pa->next;
            t = pb;
            pb = pb->next;
            free(t);
        } else if (pa->data < pb->data) {
            t = pa;
            pa = pa->next;
            free(t);
        } else {
            t = pb;
            pb = pb->next;
            free(t);
        }
    }
    if (pa != NULL) {
        pb = pa;
    }
    while (pb != NULL) {
        t = pb;
        pb = pb->next;
        free(t);
    }
    rear->next = NULL;
}

int pattern(LinkList la, LinkList lb) {
    if (la == NULL || lb == NULL)
        return 0;
    PtrToLNode pre = la;
    PtrToLNode pa = la;
    PtrToLNode pb = lb;
    while (pa != NULL && pb != NULL) {
        if (pa->data == pb->data) {
            pa = pa->next;
            pb = pb->next;
        } else {
            //pa跳回失配前的位置
            pre = pre->next;
            pa = pre;
            pb = lb;
        }
    }
    if (pb == NULL)
        return 1;
    else
        return 0;
}

//判断一个循环双链表中的数据是否对称
int isDLinkListSymmetry(DLinkList l) {
    if (l == NULL)
        return 0;
    DLinkList p = l->next;
    DLinkList q = l->prior;
    //!q->next!=p
    //pq相邻时还要交换位置再进入循环判断一次
    while (p != q && q->next != p) {
        if (p->data == q->data) {
            p = p->next;
            q = q->prior;
        } else {
            return 0;
        }
    }
    return 1;
}

//将两个循环单链表合并为一个
void linkTwoCycleList(LinkList la, LinkList lb) {
    if (lb == NULL || la == NULL)
        return;
    PtrToLNode pa = la;
    PtrToLNode pb = lb;
    while (pa->next != la)
        pa = pa->next;
    while (pb->next != lb)
        pb = pb->next;
    pa->next = lb;
    pb->next = la;
}

void findMinAndDelete_CycleList(LinkList l) {
    if (l == NULL || l->next == NULL)
        return;
    PtrToLNode p = l->next;
    PtrToLNode pre = l;
    PtrToLNode min = l->next;
    PtrToLNode minpre = l;
    //链表不空时执行循环
    while (l->next != l) {
        p = l->next;
        pre = l;
        min = p;
        minpre = pre;
        while (p != l) {
            if (p->data < min->data) {
                min = p;
                minpre = pre;
            }
            pre = p;
            p = p->next;
        }
        printf("%2d ", min->data);
        minpre->next = min->next;
        free(min);
    }
    printf("\n");
    free(l);
}

//在一个非循环双链表中，查找指定元素x，将其freq++，然后按freq向前排到最前的位置
DLinkList Locate(DLinkList l, ElementType x) {
    if (l == NULL)
        return NULL;
    DLinkList p = l->next;
    while (p != NULL) {
        if (p->data == x)
            break;
        p = p->next;
    }
    if (p == NULL)
        return NULL;
    p->freq++;
    //去掉p节点
    if (p->next != NULL) {
        p->next->prior = p->prior;
    }
    p->prior->next = p->next;
    //寻找插入位置
    DLinkList pre = p->prior;
    while (pre != l && pre->freq <= p->freq) {
        pre = pre->prior;
    }
    //插入
    p->next = pre->next;
    pre->next->prior = p;
    p->prior = pre;
    pre->next = p;
    return p;
}

//寻找带头结点的单链表的倒数第k个节点
int searchLastKth(LinkList l, int k) {
    if (l == NULL || l->next == NULL)
        return 0;
    int count = 0;
    LinkList fast = l->next;
    LinkList slow = l->next;
    while (fast != NULL) {
        //这里很巧妙地处理了k大于表长的情况
        if (count < k)
            count++;
        else
            slow = slow->next;
        fast = fast->next;
    }
    if (count < k) {
        return 0;
    } else {
        printf("last %d-th:%d\n", k, slow->data);
        return 1;
    }
}

int Length(LinkList head) {
    LinkList p = head->next;
    int len = 0;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

//寻找两个链表的公共节点，跟标准答案稍有不同，本质是一样的
LinkList findCommonPostFix(LinkList l1, LinkList l2) {
    int len1 = Length(l1);
    int len2 = Length(l2);
    printf("\nlen1=%d,len2=%d\n", len1, len2);
    LinkList fast, slow;
    int dist;
    if (len1 > len2) {
        dist = len1 - len2;
        fast = l1->next;
        slow = l2->next;
    } else {
        dist = len2 - len1;
        fast = l2->next;
        slow = l1->next;
    }
    while (dist--) {
        fast = fast->next;
    }
    //注意这里都用next判断
    while (fast->next != NULL && fast->next != slow->next) {
        fast = fast->next;
        slow = slow->next;
    }
    return fast->next;
}

int abs(int a) {
    if (a > 0)
        return a;
    else
        return -a;
}
void deduplicata_ifAbsEqual(LinkList l, int n) {
    int* mark = (int*)malloc(sizeof(int) * (1 + n));
    for (int i = 0; i < n + 1; ++i) {
        mark[i] = 0;
    }
    LinkList p = l->next;
    LinkList pre = l;
    while (p != NULL) {
        int index = abs(p->data);
        if (mark[index] == 0) {
            pre = p;
            p = p->next;
            mark[index]++;
        } else {
            LinkList t = p;
            pre->next = p->next;
            p = p->next;
            free(t);
        }
    }
    free(mark);
    return;
}

//寻找链表中的环的入口点
LinkList findLoopStart(LinkList l) {
    LinkList fast = l;
    LinkList slow = l;
    while (slow != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            break;
    }
    //如果无环，返回NULL
    if (slow == NULL || fast->next == NULL)
        return NULL;
    LinkList start = l;
    LinkList encounter = slow;
    /*
        算法的核心所在：如果有环，则令一个指针从起始点开始，另一个指针从相遇点开始，
        以相同的速度前进，最终一定会相遇在环的入口点
    */
    while (start != encounter) {
        start = start->next;
        encounter = encounter->next;
    }
    return encounter;
}

//2019年真题，自己实现的，思路很朴素，用了很多变量方便理解
//跟答案算法思路是一样的，但是感觉答案更难
LinkList reverse(LinkList l) {
    if (l == NULL || l->next == NULL)
        return l;
    LinkList dummy = (LinkList)malloc(sizeof(struct LNode));
    dummy->next = NULL;

    LinkList next;
    while (l != NULL) {
        next = l->next;
        l->next = dummy->next;
        dummy->next = l;
        l = next;
    }
    LinkList ret = dummy->next;
    free(dummy);
    return ret;
}

LinkList reorderList(LinkList l) {
    if (l == NULL || l->next == NULL || l->next->next == NULL)
        return l;
    LinkList fast = l->next;
    LinkList slow = l->next;
    LinkList slowPre;
    while (fast->next != NULL) {
        slowPre = slow;
        slow = slow->next;
        fast = fast->next;
        if (fast->next != NULL)
            fast = fast->next;
    }
    slowPre->next = NULL;
    //逆转后半部分
    LinkList q = reverse(slow);
    LinkList qNext;

    //归并
    LinkList p, pNext;
    LinkList t;
    p = l->next;
    while (p != NULL) {
        qNext = q->next;
        pNext = p->next;
        if (pNext == NULL)
            t = p;
        q->next = p->next;
        p->next = q;
        q = qNext;
        p = pNext;
    }
    if (q != NULL) {
        t = t->next;
        t->next = q;
    }
    return l;
}

测试代码

#include <stdio.h>
#include <stdlib.h>

#include "2-3-linkList.c"

LinkList initLinkListFromArray(ElementType* A, int arraySize) {
    LinkList l = (LinkList)malloc(sizeof(struct LNode));
    l->data = A[arraySize - 1];
    l->next = NULL;

    for (int i = arraySize - 2; i >= 0; --i) {
        PtrToLNode p = (PtrToLNode)malloc(sizeof(struct LNode));
        p->data = A[i];
        p->next = l;
        l = p;
    }
    return l;
}

void printLinkList(LinkList l) {
    printf("\n%s:\n", __func__);
    if (l == NULL)
        return;
    while (l) {
        printf("%2d ", l->data);
        l = l->next;
    }
    printf("\n");
}

void desoryLinkList(LinkList l) {
    PtrToLNode p;
    while (l) {
        p = l->next;
        free(l);
        l = p;
    }
}

void test_deleteX_recursively() {
    printf("\n%s:\n", __func__);
    int a[6] = {1, 2, 3, 2, 4, 2};
    LinkList l = initLinkListFromArray(a, 6);
    printLinkList(l);
    deleteX_recursively(&l, 2);
    printLinkList(l);
    desoryLinkList(l);
}

void test_deleteX_linkListWithHead() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[5] = {3, 2, 1, 2, 2};
    head->next = initLinkListFromArray(a, 5);
    printLinkList(head->next);
    deleteX_linkListWithHead(head, 2);
    printLinkList(head->next);
    desoryLinkList(head->next);

    int b[5] = {2, 2, 2, 2, 2};
    head->next = initLinkListFromArray(b, 5);
    printLinkList(head->next);
    deleteX_linkListWithHead(head, 2);
    printLinkList(head->next);
    desoryLinkList(head);
}

void test_printList_inversely() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[5];
    for (int i = 0; i < 5; ++i)
        a[i] = i + 1;
    head->next = initLinkListFromArray(a, 5);
    printLinkList(head->next);
    printList_inversely(head);
    printf("\n");
    desoryLinkList(head);
}

void test_deleteMin() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[6];
    for (int i = 0; i < 6; ++i)
        a[i] = rand() % (i + 10);
    head->next = initLinkListFromArray(a, 6);
    printLinkList(head->next);
    printLinkList(deleteMin(head)->next);
    desoryLinkList(head);
}

void test_reverseLinkList() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[6];
    for (int i = 0; i < 6; ++i)
        a[i] = i + 1;
    head->next = initLinkListFromArray(a, 6);
    printLinkList(head->next);
    reverseLinkList(head);
    printLinkList(head->next);
    desoryLinkList(head);
}

void test_InsertionSort() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[16];
    for (int i = 0; i < 16; ++i)
        a[i] = rand() % (i + 32);
    head->next = initLinkListFromArray(a, 16);
    printLinkList(head->next);
    InsertionSort(head);
    printLinkList(head->next);
    desoryLinkList(head);
}

void test_rangeDelete() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[16];
    for (int i = 0; i < 16; ++i)
        a[i] = rand() % (i + 32);
    head->next = initLinkListFromArray(a, 16);
    printLinkList(head->next);
    rangeDelete(head, 0, 10);
    printLinkList(head->next);
    desoryLinkList(head);
}

void test_searchFirstCommon() {
    printf("\n%s:\n", __func__);

    int a[8];
    for (int i = 0; i < 8; ++i)
        a[i] = rand() % (i + 16);
    LinkList common = initLinkListFromArray(a, 8);

    int b[4];
    for (int i = 0; i < 4; ++i)
        b[i] = rand() % (2 * i + 19);
    LinkList l1 = initLinkListFromArray(b, 4);
    PtrToLNode p = l1;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = common;

    int c[7];
    for (int i = 0; i < 7; ++i)
        c[i] = rand() % (i / 2 + 23);
    LinkList l2 = initLinkListFromArray(c, 7);
    p = l2;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = common;

    printLinkList(l1);
    printLinkList(l2);
    PtrToLNode result = searchFirstCommon(l1, l2);
    printf("\vcommon:%d\n", result->data);
    desoryLinkList(l1);
    //desoryLinkList(l2);
}

void test_findMinAndDelete() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[5] = {8, 3, 5, 7, 1};
    head->next = initLinkListFromArray(a, 5);
    printLinkList(head->next);
    findMinAndDelete(head);
    printf("\n");
}

void test_splitLinkList() {
    printf("\n%s:\n", __func__);
    PtrToLNode head1 = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode head2;

    int a[6] = {8, 5, 3, 7, 1, 2};
    head1->next = initLinkListFromArray(a, 6);
    printLinkList(head1->next);
    head2 = splitLinkList(head1);
    printLinkList(head1->next);
    printLinkList(head2->next);
    desoryLinkList(head1);
    desoryLinkList(head2);
}

void test_splitLinkList_2() {
    printf("\n%s:\n", __func__);
    PtrToLNode head1 = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode head2;

    int a[8];
    for (int i = 0; i < 8; ++i) {
        a[i] = i;
    }

    head1->next = initLinkListFromArray(a, 6);
    printLinkList(head1->next);
    head2 = splitLinkList_2(head1);

    printLinkList(head1->next);
    printLinkList(head2->next);
    desoryLinkList(head1);
    desoryLinkList(head2);
}

void test_deduplicateInOrderedList() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[10] = {7, 10, 10, 21, 30, 42, 42, 42, 51, 70};
    head->next = initLinkListFromArray(a, 10);
    printLinkList(head->next);
    deduplicateInOrderedList(head);
    printLinkList(head->next);
    desoryLinkList(head);
}

void test_mergeList() {
    printf("\n%s:\n", __func__);
    PtrToLNode head1 = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode head2 = (PtrToLNode)malloc(sizeof(struct LNode));
    int a[6] = {1, 3, 4, 7, 10, 11};
    int b[4] = {2, 5, 8, 9};
    head1->next = initLinkListFromArray(a, 6);
    head2->next = initLinkListFromArray(b, 4);
    printLinkList(head1->next);
    printLinkList(head2->next);
    mergeList(head1, head2);
    printLinkList(head1->next);
    desoryLinkList(head1);
}

void test_getCommon() {
    printf("\n%s:\n", __func__);
    PtrToLNode head1 = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode head2 = (PtrToLNode)malloc(sizeof(struct LNode));
    int a[7] = {1, 2, 3, 4, 5, 6, 7};
    int b[5] = {1, 3, 4, 7, 9};
    head1->next = initLinkListFromArray(a, 7);
    head2->next = initLinkListFromArray(b, 5);
    printLinkList(head1->next);
    printLinkList(head2->next);
    PtrToLNode head3 = getCommon(head1, head2);
    printLinkList(head3->next);
    desoryLinkList(head1);
    desoryLinkList(head2);
    desoryLinkList(head3);
}

void test_intersection() {
    printf("\n%s:\n", __func__);
    PtrToLNode head1 = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode head2 = (PtrToLNode)malloc(sizeof(struct LNode));
    int a[8] = {1, 2, 3, 4, 12, 32, 43, 56};
    int b[5] = {2, 3, 43, 55, 56};
    head1->next = initLinkListFromArray(a, 8);
    head2->next = initLinkListFromArray(b, 5);
    printLinkList(head1->next);
    printLinkList(head2->next);
    intersection(head1, head2);
    printLinkList(head1->next);
    desoryLinkList(head1);
}

void test_pattern() {
    printf("\n%s:\n", __func__);
    int a[7] = {1, 2, 3, 4, 3, 4, 5};
    int b[3] = {3, 4, 5};
    int c[7] = {1, 2, 3, 4, 3, 5, 5};
    LinkList la = initLinkListFromArray(a, 7);
    LinkList lb = initLinkListFromArray(b, 3);
    LinkList lc = initLinkListFromArray(c, 7);
    printLinkList(la);
    printLinkList(lb);
    printLinkList(lc);
    printf("\npattern la with lb:%d\n", pattern(la, lb));
    printf("\npattern la with lc:%d\n", pattern(la, lc));
    desoryLinkList(la);
    desoryLinkList(lb);
    desoryLinkList(lc);
}

void test_isDLinkListSymmetry() {
    DLinkList head = (DLinkList)malloc(sizeof(struct DNode));
    DLinkList dn[6];
    //制造一个循环双链表
    for (int i = 0; i < 6; ++i) {
        dn[i] = malloc(sizeof(struct DNode));
        dn[i]->data = (2 * i - 5) * (2 * i - 5);
    }
    head->next = dn[0];
    dn[0]->prior = head;
    head->prior = dn[5];
    dn[5]->next = head;
    //把指针串接起来
    for (int i = 0; i < 5; ++i) {
        dn[i]->next = dn[i + 1];
        dn[5 - i]->prior = dn[4 - i];
    }
    DLinkList p;
    //正向打印
    p = head->next;
    while (p != head) {
        printf("%2d ", p->data);
        p = p->next;
    }
    printf("\n");
    //逆向打印
    p = head->prior;
    while (p != head) {
        printf("%2d ", p->data);
        p = p->prior;
    }
    //判断是否对称
    printf("\nisDLinkListSymmetry:%d\n", isDLinkListSymmetry(head));

    //改变一个数据，使之不对称，重复上述操作
    dn[2]->data = 2;
    p = head->next;
    while (p != head) {
        printf("%2d ", p->data);
        p = p->next;
    }
    printf("\n");
    p = head->prior;
    while (p != head) {
        printf("%2d ", p->data);
        p = p->prior;
    }
    printf("\nisDLinkListSymmetry:%d\n", isDLinkListSymmetry(head));
}

void test_linkTwoCycleList() {
    printf("\n%s:\n", __func__);
    int a[8] = {1, 2, 3, 4, 12, 32, 43, 56};
    int b[5] = {2, 3, 43, 55, 56};
    LinkList l1 = initLinkListFromArray(a, 8);
    LinkList l2 = initLinkListFromArray(b, 5);
    printLinkList(l1);
    printLinkList(l2);
    PtrToLNode p;
    p = l1;
    while (p->next != NULL)
        p = p->next;
    p->next = l1;

    p = l2;
    while (p->next != NULL)
        p = p->next;
    p->next = l2;
    linkTwoCycleList(l1, l2);

    printf("\nafter linkTwoCycleList:\n");
    p = l1;
    while (p->next != l1) {
        printf("%2d ", p->data);
        p = p->next;
    }
    printf("%2d ", p->data);
    printf("\n");
    //desoryLinkList(l1);
}

void test_findMinAndDelete_CycleList() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[10];
    for (int i = 0; i < 10; ++i) {
        a[i] = rand() % (3 * i + 37);
    }
    head->next = initLinkListFromArray(a, 10);
    printLinkList(head->next);
    //让链表循环起来
    PtrToLNode p;
    p = head->next;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = head;
    findMinAndDelete_CycleList(head);
}

void test_Locate() {
    DLinkList head = (DLinkList)malloc(sizeof(struct DNode));
    DLinkList dn[4];
    //制造一个双链表
    for (int i = 0; i < 4; ++i) {
        dn[i] = malloc(sizeof(struct DNode));
        dn[i]->freq = 0;
        dn[i]->data = 2 * i + 1;
    }
    head->next = dn[0];
    dn[0]->prior = head;
    head->prior = NULL;
    dn[3]->next = NULL;
    //把指针串接起来
    for (int i = 0; i < 3; ++i) {
        dn[i]->next = dn[i + 1];
        dn[3 - i]->prior = dn[2 - i];
    }
    DLinkList p;
    //正向打印
    p = head->next;
    while (p != NULL) {
        printf("data=%2d,freq=%2d\n", p->data, p->freq);
        p = p->next;
    }
    p = Locate(head, 3);
    printf("Locate(head,3):%d\n", p->data);
    p = Locate(head, 7);
    printf("Locate(head,7):%d\n", p->data);
    p = Locate(head, 7);
    printf("Locate(head,7):%d\n", p->data);

    p = head->next;
    while (p != NULL) {
        printf("data=%2d,freq=%2d\n", p->data, p->freq);
        p = p->next;
    }

    p = Locate(head, 3);
    printf("Locate(head,3):%d\n", p->data);

    p = head->next;
    while (p != NULL) {
        printf("data=%2d,freq=%2d\n", p->data, p->freq);
        p = p->next;
    }
    printf("\n");
}

void test_searchLastKth() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[10];
    for (int i = 0; i < 10; ++i) {
        a[i] = rand() % (3 * i + 37);
    }
    head->next = initLinkListFromArray(a, 10);
    printLinkList(head->next);
    printf("searchLastKth returns:%d\n", searchLastKth(head, 3));
    desoryLinkList(head);
}

void test_findCommonPostFix() {
    printf("\n%s:\n", __func__);
    PtrToLNode head1 = (PtrToLNode)malloc(sizeof(struct LNode));
    PtrToLNode head2 = (PtrToLNode)malloc(sizeof(struct LNode));
    int a[11] = {1, 3, 5, 7, 9, 9, 9, 9, 32, 43, 56};
    int b[5] = {0, 2, 4, 6, 8};
    head1->next = initLinkListFromArray(a, 11);
    head2->next = initLinkListFromArray(b, 5);
    //制造公共后缀
    PtrToLNode p, q;
    p = head1->next;
    q = head2->next;
    while (q->next != NULL) {
        q = q->next;
    }
    //在32这个位置穿起来
    while (p != NULL && p->data != 32) {
        p = p->next;
    }
    q->next = p;
    printLinkList(head1->next);
    printLinkList(head2->next);

    PtrToLNode commonPostFix = findCommonPostFix(head1, head2);
    printLinkList(commonPostFix);

    desoryLinkList(head1);
    //desoryLinkList(head1);
}

void test_deduplicata_ifAbsEqual() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[5] = {21, -15, -15, -7, 15};
    head->next = initLinkListFromArray(a, 5);
    printLinkList(head->next);
    deduplicata_ifAbsEqual(head, 15);
    printLinkList(head->next);
    desoryLinkList(head);
}

void test_findLoopStart() {
    printf("\n%s:\n", __func__);

    int a[10];
    for (int i = 0; i < 10; ++i) {
        a[i] = i;
    }
    PtrToLNode l = initLinkListFromArray(a, 10);
    printLinkList(l);
    //定位到尾节点
    PtrToLNode rear = l;
    while (rear->next != NULL)
        rear = rear->next;
    //定位到第5个节点，为环的入口
    int count = 5;
    PtrToLNode p = l;
    while (count-- != 0)
        p = p->next;
    //成环
    rear->next = p;
    //打印20次凑活观察一下
    p = l;
    count = 20;
    while (count-- != 0) {
        printf("%2d ", p->data);
        p = p->next;
    }
    //调用算法找到环的入口
    p = findLoopStart(l);
    printf("\nfindLoopStart:%d\n", p->data);
    //desoryLinkList(l);
}

void test_reorderList() {
    printf("\n%s:\n", __func__);
    PtrToLNode head = (PtrToLNode)malloc(sizeof(struct LNode));

    int a[6] = {1, 2, 3, 4, 5, 6};
    head->next = initLinkListFromArray(a, 6);
    printLinkList(head->next);

    head = reorderList(head);
    printLinkList(head->next);
    desoryLinkList(head->next);

    int b[5] = {1, 2, 3, 4, 5};
    head->next = initLinkListFromArray(b, 5);
    printLinkList(head->next);

    head = reorderList(head);
    printLinkList(head->next);
    desoryLinkList(head);
}
int main(int argc, char* argv[]) {
    //test_deleteX_recursively();
    //test_deleteX_linkListWithHead();
    //test_printList_inversely();
    //test_deleteMin();
    //test_reverseLinkList();
    //test_InsertionSort();
    //test_rangeDelete();
    //test_searchFirstCommon();
    //test_findMinAndDelete();
    //test_splitLinkList();
    //test_splitLinkList_2();
    //test_deduplicateInOrderedList();
    //test_mergeList();
    //test_getCommon();
    //test_intersection();
    //test_pattern();
    //test_isDLinkListSymmetry();
    //test_linkTwoCycleList();
    //test_findMinAndDelete_CycleList();
    //test_Locate();
    //test_searchLastKth();
    //test_findCommonPostFix();
    //test_deduplicata_ifAbsEqual();
    //test_findLoopStart();
    test_reorderList();
    return 0;
}