线性结构 - 链表练习

题⽬1

将两个递增的有序链表合并为⼀个链表的有序链表;

要求

结果链表仍然使用两个链表的存储空间
不另外占⽤用其他的存储空间
表中不允许有重复的数据

思路：递归法

根据题目要求：

终止条件：两个链表都为空时，表示我们对链表已经完成合并
递归内容：我们判断pa和pb的首元结点值哪个更小，然后较小结点的next指针指向其余结点的合并结果（调用递归）

2020-04-09 152316

复杂度：

时间复杂度：O(n+m)，其中n为La的长度，m为Lb的长度
空间复杂度：O(n+m)，其中n为La的长度，m为Lb的长度

代码实现：

LinkList mergeTwoList(LinkList La, LinkList Lb) {
    Node *pa = La;
    Node *pb = Lb;
    
    if (pa == NULL) {
        return pb;
    }
    if (pb == NULL) {
        return pa;
    }
    
    if (pa->data <= pb->data) {
        pa->next = mergeTwoList(pa->next, pb);
        return pa;
    }
    pb->next = mergeTwoList(pa, pb->next);
    return pb;
}

void mergeList(LinkList *La, LinkList *Lb) {
    if (La == NULL || Lb == NULL) {
        return;
    }
  
    Node *Lc = (*La);       /* 借用La的头结点 */
    Node *pa = (*La)->next; /* 从首元结点开始合并 */
    Node *pb = (*Lb)->next;
    
    /* 新链表的头结点指向合并后的首元结点 */
    Lc->next = mergeTwoList(pa, pb);
    *La = Lc;
}

int main(int argc, const char * argv[]) {   
 
    Status iStatus;
    LinkList La,Lb, L;
    InitList(&La);
    InitList(&Lb);
    for(int j = 10;j>=0;j-=2)
    {
        iStatus = ListInsert(&La, 1, j);
    }
    printf("La:\n");
    ListTraverse(La);

    for(int j = 11;j>0;j-=2)
    {
        iStatus = ListInsert(&Lb, 1, j);
    }
    printf("Lb:\n");
    ListTraverse(Lb);

    mergeList(&La, &Lb);
    printf("Lc:\n");
    ListTraverse(La);
}

输出结果：

La:
0  2  4  6  8  10  
Lb:
1  3  5  7  9  11  
Lc:
0  1  2  3  4  5  6  7  8  9  10  11

题目2

已知两个链表A和B分别表示两个集合，其元素递增排列。设计⼀个算法，用于求出A与B的交集，并存储在A链表中。例如 : La = {2,4,6,8}; Lb = {4,6,8,10}; 输出La = {4,6,8}。

思路：这题和题目1非常的相似，同样使用递归

终止条件：两个链表都为空时，表示我们求出交集链表
递归内容：当pa和pb的首元结点值相等时，将pa的next指针指向pa，pb其余结点的交集（调用递归）

复杂度：

时间复杂度：O(n+m)，其中n为La的长度，m为Lb的长度
空间复杂度：O(n+m)，其中n为La的长度，m为Lb的长度

代码实现：

LinkList intersectionTwoList(LinkList La, LinkList Lb) {
    Node *pa = La;
    Node *pb = Lb;
    
    if (pa == NULL || pb == NULL) {
        return NULL;
    }
    
    if (pa->data == pb->data) {
        pa->next = intersectionTwoList(pa->next, pb->next);
        return pa;
    }else if (pa->data < pb->data) {
        pa = pa->next;
        return intersectionTwoList(pa, pb);
    }else {
        pb = pb->next;
        return intersectionTwoList(pa, pb);
    }
}

void intersection(LinkList *La, LinkList *Lb) {
    if (La == NULL || Lb == NULL) {
        return;
    }
    Node *Lc = (*La);
    Node *pa = (*La)->next;
    Node *pb = (*Lb)->next;
    
    Lc->next = intersectionTwoList(pa, pb);
    *La = Lc;
}

int main(int argc, const char * argv[]) {   
    
  	Status iStatus;
    LinkList La,Lb, L;
    InitList(&La);
    InitList(&Lb);
  
    ListInsert(&La, 1, 8);
    ListInsert(&La, 1, 6);
    ListInsert(&La, 1, 4);
    ListInsert(&La, 1, 2);
    printf("La:\n");
    ListTraverse(La);

    ListInsert(&Lb, 1, 10);
    ListInsert(&Lb, 1, 8);
    ListInsert(&Lb, 1, 6);
    ListInsert(&Lb, 1, 4);
    ListInsert(&Lb, 1, 3);
    printf("Lb:\n");
    ListTraverse(Lb);

    intersection(&La, &Lb);
    printf("Lc:\n");
    ListTraverse(La);
}

输出：

La:
2  4  6  8  
Lb:
3  4  6  8  10  
Lc:
4  6  8

题目3

设计一个算法，将链表中所有节点的链接方向"原地旋转"。

例如：L={0,2,4,6,8,10}，逆转后: L = {10,8,6,4,2,0}

要求：

利用原表的存储空间。换句话说，要求算法空间复杂度为O(1)

思路一：利用头插法构建链表，得到的链表就是逆序存储。（迭代思想）

复杂度：

时间复杂度：O(n)，n是链表L的结点个数
空间复杂度：O(1)

代码如下：

void inverse(LinkList *L) {
    if (L == NULL) {
        return;
    }
  
    // 头插法
    Node *p, *q;
    // p指向首元结点
    p = (*L)->next;
    // 头结点的后继结点置空
    (*L)->next = NULL;
    
    while (p) {
        // q指向p的后继结点
        q = p->next;
        
        // p的后继指针指向*L的后继结点
        p->next = (*L)->next;
        
        // *L的后继指针指向p
        (*L)->next = p;
        
        // p指向q
        p = q;
    }
}

int main(int argc, const char * argv[]) {   
    
  	Status iStatus;
    LinkList L;
  
    InitList(&L);
    for(int j = 10;j>=0;j-=2)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L逆转前:\n");
    ListTraverse(L);

    inverse(&L);
    printf("L逆转后:\n");
    ListTraverse(L);
}

输出：

L逆转前:
0  2  4  6  8  10  
L逆转后:
10  8  6  4  2  0

思路二：递归法

终止条件：如果链表只有一个节点的时候反转也是它自己，直接返回即可
递归内容：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。用last接收

复杂度：

时间复杂度：O(n)，n是链表L的结点个数
空间复杂度：O(n), n是链表L的结点个数

代码如下：

Node* reverse(Node *head) {
    if (head->next == NULL) {
        return head;
    }
    Node *last = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return last;
}

void inverse(LinkList *L) {
    if (L == NULL) {
        return;
    }
    Node *head = *L;
    (*L)->next = reverse(head->next);
}

int main(int argc, const char * argv[]) {   
  	
  	Status iStatus;
    LinkList L;
  
    InitList(&L);
    for(int j = 10;j>=0;j-=2)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L逆转前:\n");
    ListTraverse(L);

    inverse(&L);
    printf("L逆转后:\n");
    ListTraverse(L);
}

输出：

L逆转前:
0  2  4  6  8  10  
L逆转后:
10  8  6  4  2  0

题目4

设计⼀个算法，删除递增有序链表中值大于等于mink且⼩于等于maxk的所有元素。(mink、maxk是给定的两个参数，值可以和表中的元素相同，也可以不同)

思路：迭代删除链表结点

复杂度：

时间复杂度：O(n)， n是链表L的结点个数
空间复杂度：O(1)

代码如下：

void deleteMinMax(LinkList *L, int mink, int maxk) {
    if (L == NULL) {
        return;
    }
    Node *pre = *L, *cur = (*L)->next, *temp;
    while (cur) {
        if (mink <= cur->data && cur->data <= maxk) {
            temp = cur;
            pre->next = cur->next;
            cur = cur->next;
            free(temp);
        }else {
            pre = cur;
            cur = cur->next;
        }
    }
}

int main(int argc, const char * argv[]) {   
 
    Status iStatus;
    LinkList L;
  
    InitList(&L);
    for(int j = 10;j>=0;j-=2)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L链表:\n");
    ListTraverse(L);

    DeleteMinMax(&L, 4, 10);
    printf("删除链表mink与maxk之间结点的链表:\n");
    ListTraverse(L);
}

输出：

L链表:
0  2  4  6  8  10  
删除链表mink与maxk之间结点的链表:
0  2

题目5

设将n(n>1)个整数存放到⼀维数组R中，试设计⼀个在时间和空间两⽅面都尽可能高效的算法。

将R中保存的序列循环左移p个位置(0<p<n)个位置，即将R中的数据由(x0,x1,......,xn-1)变换为 (xp,xp+1,...,xn-1,x0,x1,...,xp-1)。

例如：

pre[10] = {0,1,2,3,4,5,6,7,8,9}

n = 10,p = 3

pre[10] = {3,4,5,6,7,8,9,0,1,2}

思路：数组反转

先将n个数据原地逆置; 9,8,7,6,5,4,3,2,1,0
将n个数据拆解成[n-1, n-p] 和 [n-p-1, 0]; [9,8,7,6,5,4,3], [2,1,0]
再将[n-1, n-p] 和 [n-p-1, 0]分别逆置；[3,4,5,6,7,8,9,0,1,2]

复杂度：

时间复杂度：O(n)，n是整数的个数
空间复杂度：O(1)

代码如下：

void reverseArr(int *pre, int left, int right) {
    int i = left, j = right;
    int temp;
    while (i < j) {
        temp = pre[i];
        pre[i] = pre[j];
        pre[j] = temp;
        
        i++;
        j--;
    }
}

void leftShift(int *pre, int n, int p) {
    if (p > 0 && p < n) {
        reverseArr(pre, 0, n-1);      /* 1. 将数组中所有元素全部逆置 */
        reverseArr(pre, 0, n-p-1);  /* 2. 将前n-p个数据逆置 */
        reverseArr(pre, n-p, n-1);    /* 3. 将后p个数据逆置 */
    }
}

int main(int argc, const char * argv[]) {   
 
    int pre[10] = {0,1,2,3,4,5,6,7,8,9};
    leftShift(pre, 10, 3);
    for (int i=0; i < 10; i++) {
        printf("%d ",pre[i]);
    }
}

题目6

已知⼀个整数序列列A = (a0,a1,a2,...an-1)，其中0<=ai<=n, 0<=i<=n。若存在ap1= ap2 = ...=apm = x，且m>n/2, 0<=pk<n,1<=k<=m，则称x为A的主元素。

例如，A=(0,5,5,3,5,7,5,5)，则5是主元素; 若B=(0,5,5,3,5,1,5,7)，则B中没有主元素。

假设A中的n个元素保存在⼀个一维数组中，请设计⼀个尽可能⾼效的算法，找出数组元素中的主元素，若存在主元素则输出该元素，否则输出-1。

题解：主元素是指在数组中出现次数超过一半的元素，即主元素是数组中的众数，并且满足元素个数超过数组长度的一半

思路：Boyer-Moore 投票算法（求众数）

如果我们把主元素记为 +1，把其他数记为−1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出主元素比其他数多。
Boyer-Moore 算法的本质和分治法十分类似。我们首先给出 Boyer-Moore 算法的详细步骤：

我们维护一个候选主元素 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
- 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
- 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
在遍历完成后，candidate 即为整个数组的出现次数最多的元素。

复杂度：

时间复杂度：O(n)
空间复杂度：O(1)

代码如下：

int majorityElement(int *nums, int n) {
    int candidate = -1;
    int count = 0;
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        if (num == candidate)
            ++count;
        else if (--count < 0) {
            int num = nums[i];
            candidate = num;
            count = 1;
        }
    }
    
    // 出现较多，但不一定满足主元素数量>n/2的条件
    if (count > 0) {
        int total = 0;
        for (int i = 1; i < n; i++)
            if (nums[i] == candidate) ++total;
        if (total > n / 2)
            return candidate;
    }
    return -1;
}

int main(int argc, const char * argv[]) {   
 
    int  A[] = {0,5,5,3,5,7,5,5};
    int  B[] = {0,5,5,3,5,1,5,7};
    int  C[] = {0,1,2,3,4,5,6,7};
    
    int value = majorityElement(A, 8);
    printf("数组A 主元素为: %d\n",value);
    value = majorityElement(B, 8);
    printf("数组B 主元素为(-1表示数组没有主元素): %d\n",value);
    value = majorityElement(C, 8);
    printf("数组C 主元素为(-1表示数组没有主元素): %d\n",value); 
}

输出：

数组A 主元素为: 5
数组B 主元素为(-1表示数组没有主元素): -1
数组C 主元素为(-1表示数组没有主元素): -1

题目7

⽤单链表保存m个整数，结点的结构为(data, link)，且|data|<=n(n为正整数)。现在要去设计一个时间复杂度尽可能高效的算法。对于链表中的data绝对值相等的结点，仅保留第⼀次出现的结点，删除其余绝对值相等的结点。

例如，链表A = {21,-15,15,-7,15}，删除后的链表A={21,-15,-7}。

思路：

创建一个大小为n+1的辅助数组t，初始化为0
从首元结点开始遍历链表，依次检查t[|data|]的值
- t[|data|] == 0，结点首次出现，保留该结点，并将 t[|data|] 赋值为1
- t[|data|] != 0，则将该结点删除

复杂度：

时间复杂度: O(m)，对长度为m的链表进行一趟遍历,则算法时间复杂度为O(m)
空间复杂度: O(n)

代码如下：

void deleteEqualNode(LinkList *L, int n) {
    char *flag = calloc(n + 1, sizeof(char));
    if (flag == NULL) {
        return;
    }
    
    for (int i = 0; i < n; i++) {
        *(flag + i) = 0;
    }
    
    // 遍历链表
    Node *pre = *L;
    Node *cur = (*L)->next;
    while (cur) {
        if (flag[abs(cur->data)] == 1) {
            // 删除当前结点
            pre->next = cur->next;
            free(cur);
            cur = pre->next;
            
        }else {
            flag[abs(cur->data)] = 1;
            pre = cur;
            cur = cur->next;
        }
    }
}

查看demo