1.线性表

题目1：在顺序表的第 i 个位置前增加一个元素e。

#include <stdio.h>
#define MAX_SIZE 100
​
/**
* 题目：在顺序表的第i个位置前增加一个元素e
*/
​
/**
* 定义顺序表
*/
typedef struct {
    int element[MAX_SIZE];
    int length;
} SqList;
​
/**
* 插入
*/
void insert(SqList* list, int idx,int e) {
    
    // 顺序表为空或者满就不允许插入了 
    if(list->length <= 0 || list->length >= MAX_SIZE) {
        return;
    }
    
    // 由于没有IDE的检查,这个i要定义在外边注意！ 
    int i;
    
    // 注意画图看临界条件
    for(i = list->length; i >= idx; i--) {
        list->element[i] = list->element[i-1];
    }
    list->element[i] = e;
    
    // 最后元素的长度要加1,不要忘记了 
    list->length++;
}

题目2：设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。

基本思路：插入排序的插入算法。

#include <stdio.h>
#define MAX_SIZE 100
​
​
/**
* 题目：设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。
*/
​
/**
* 定义顺序表
*/
typedef struct {
    int element[MAX_SIZE];
    int length;
} SqList;
​
/**
* 插入算法 
*/ 
void insert(SqList* list, int elem) {
​
    // 题目中数组都已经递减了,不用判断数组为空,直接判断是否满即可
    if(list->length >= MAX_SIZE)
        return;
​
    // 让i初始指向数组最后元素的下一个位置
    // 如果插入的元素恰好是更小的元素可以直接在这里插入了 
    int i = list->length;
    
    while(elem > list->element[i-1] && i > 0) {
        list->element[i] = list->element[i-1];
        i--;
    }
    
    // 将待插入元素放到合适的位置 
    list->element[i] = elem;
    
    // 这里千万不要忘记了加1！  
    list->length++;
}

题目3：删除顺序表中所有值为e的元素

基本思路：

• 从左到右遍历顺序表，设置计数器k，用k记录元素e的个数，若遍历的当前值不是e，则往前移动k个位置。

• 后边元素覆盖前边（回退法）。

#include <stdio.h>
#define MAX_SIZE 100
​
/**
* 题目：删除顺序表中所有值为e的元素
*/
​
typedef struct {
    int element[MAX_SIZE];
    int length;
} SqList;
​
/**
* 删除
*/
void deleteElem(SqList* list, int e) {
    
    // 数组中没有元素下面的代码不用执行了 
    if(list->length <= 0) return;
    
    // i代表数组的下标 
    int i;
    
    // k代表计数器 
    int k = 0;
    
    for(i = 0; i < list->length; i++) {
        if(list->element[i] == e) {
            k++;
        } else {
            list->element[i-k] = list->element[i];
            
        }
    }
    list->length -= k;
}

举一反三：

1、删除顺序表中所有在s和t之间的元素。

/**
* 删除
*/
void deleteElem(SqList* list, int e) {
    
    // 数组中没有元素下面的代码不用执行了 
    if(list->length <= 0) return;
    
    // i代表数组的下标 
    int i;
    
    // k代表计数器 
    int k = 0;
    
    for(i = 1; i < list->length; i++) {
        // 注意：条件修改！
        if(list->element[i] >= s && list->element[i] <= t) {
            k++;
        } else {
            list->element[i-k] = list->element[i];
        }
    }
​
    list->length -= k;
}

2、删除有序顺序表中所有重复的元素。

若删除无序顺序表中所有重复的元素呢？？

先排序，再用该算法删除即可。

/**
* 删除
*/
void deleteElem(SqList* list, int e) {
    
    // 数组中没有元素下面的代码不用执行了 
    if(list->length <= 0) return;
    
    // i代表数组的下标 
    int i;
    
    // k代表计数器 
    int k = 0;
    
    for(i = 1; i < list->length; i++) {
        // 注意：条件修改
        if(list->element[i] == list->element[i-1]) {
            k++;
        } else {
            list->element[i-k] = list->element[i];
        }
    }
​
    list->length -= k;
}

题目4：求单链表中结点的个数

/**
* 题目：求单链表中所有结点的个数
*/
​
/**
* 定义结点
*/
typedef struct _node {
    int data;
    struct _node* next;
} Node;
​
/**
* 计算结点个数
*/
int getNodeNum(Node* x) {
​
    if(x == NULL) return 0;            // 当前结点为空,直接退出
​
    Node* p;                           // 计数器
    int cnt = 0;
​
    for(p = x; p; p = p->next) {
        cnt++;
    }
    return cnt;
}

题目5：单链表的反转

/**
* 题目：单链表反转
*/
​
/**
* 定义结点
*/
typedef struct _node {
    int data;
    struct _node* next;
} Node;
​
/**
* 定义单链表
*/
typedef struct _list {
    Node* head;                        // 头指针
    Node* tail;                        // 尾指针
} LinkedList;
​
/*
* 单链表反转
*/
void reverse(LinkedList* list) {
    
    // 单链表不存在 或 只有一个结点 不需要反转
    if(list->head == NULL || list->head->next == NULL) return;
​
    Node* n = NULL;                    // p左边的结点 
    Node* p = list->head;              // 待反转结点 
    Node* q;                           // p右边的结点 
​
    while(p) {
        q = p->next;
        p->next = n;
        n = p;
        p = q;
    }
​
    // 一定要交换头尾指针 
    Node* temp = list->head;
    list->head = list->tail;
    list->tail = temp;
}

题目6：查找单链表倒数第k个结点

基本思路：

• 定义快慢两个指针，先让快指针先走k步；

• 然后快慢指针一起走，当慢指针到达最后一个结点时，慢指针的位置就是倒数第k个结点的位置。

• 边界条件：k==0 和 k超出单链表的最大长度。

/**
* 题目：查找单链表倒数第k个结点
*/
​
/**
* 定义结点
*/
typedef struct _node {
    int data;
    struct _node* next;
} Node;
​
/**
* 定义单链表
*/
typedef struct _list {
    Node* head;
    Node* tail;
} LinkedList;
​
/**
* 获得倒数第k个结点
*/
Node* getNode(LinkedList* list, int k) {
​
    if(list->head == NULL || k == 0) {   // 单链表不存在 或 k==0 就返回空
        printf("单链表为空或k的值出错！\n");
        return NULL;
    }
​
​
    Node* slow = list->head;             // 慢指针
    Node* fast = list->head;             // 快指针
​
    int step = 1;
    while(step < k && fast) {            // 快指针向前走的位置
        fast = fast->next;
        step++;                          // 这里注意一定要加1
    }
​
    if(fast == NULL) {                   // 超出单链表的长度
        printf("超出单链表长度了!\n");
        return NULL;
    }
​
    while(fast->next) {                  // 快慢指针一起走
        fast = fast->next;
        slow = slow->next;
    }
​
    return slow;
}

题目7：获得单链表的中间结点

基本思路：

• 定义快慢两个指针，快指针每次走两步，慢指针每次走一步，当快指针到达终点时，慢指针到达中间。

• 边界条件：单链表的长度为奇数（偶数）和 头结点为NULL。

/**
* 题目：获得单链表的中间结点
*/

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;


/**
* 定义单链表
*/
typedef struct _list {
	Node* head;
	Node* tail;
} LinkedList;

/**
* 获得单链表的中间结点 
*/
Node* middleNode(LinkedList* list) {
	
	if(list->head == NULL) return NULL;       // 头结点为空直接返回空 
	
	Node* slow = list->head;                  // 定义快指针 
	Node* fast = list->head;                  // 定义慢指针
	
    // 这里边界条件要注意
	while(fast && fast->next) {
		fast = fast->next->next;              // 快指针每次走两步 
		slow = slow->next;                    // 慢指针每次走一步 
	}
	
	return slow;		
} 

题目8：从尾到头打印单链表（单链表的递归遍历）

基本思路：

• 对于这种颠倒顺序的问题，我们要立刻想到栈，先进后出。

• 所以，要么自己定义栈，要么使用系统栈，系统栈就是递归了。

/**
* 题目：从尾到头打印单链表
*/

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 单链表的递归遍历(从尾到头) 
*/
void rPrintList(Node* node) {
	if(node == NULL) return;
	rPrintList(node->next);
	printf("%d\n", node->data);	
}

单链表的递归遍历（从头到尾）：

/**
* 单链表的递归遍历(从头到尾)
*/
void rPrintList(Node* node) {
	if(node == NULL) return;
	printf("%d\n", node->data);
	rPrintList(node->next》);		
}

题目9：判断两个单链表是否相交

基本思路：

• 两个单链表相交于某一点，那么在这个相交结点之后的所有结点都是这两个单链表共有的。即，如果两个单链表相交，那么最后一个结点肯定是共有的。

/**
* 题目：判断两个单链表是否相交
*/

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 判断两个单链表是否相交
*/
int hasPublicNode(Node* n1, Node* n2) {
    
    // 有一个单链表不存在直接返回0
    if(n1 == NULL || n2 == NULL) return 0;
    
    // 遍历链表1
    Node* p1 = n1;
    while(p1) {
        p1 = p1->next;
    }
    
    // 遍历链表2
    Node* p2 = n2;
    while(p2) {
        p2 = p2->next;
    }
    
    // 比较两条单链表的最后结点的地址
    return p1 == p2;
}

题目10：给出一单链表头指向pHead和一个结点指向pToBeDeleted，O(1)时间复杂度删除结点pToBeDeleted。

基本思路：

• 正常想法是让该结点的前一个结点指向该结点的下一个结点，这种情况需要遍历找到该结点的前一个结点，时间复杂度为O(n)。

• 对于链表，链表中的每个结点结构都是一样的，可以把该结点的下一个结点的数据复制到该结点，然后删除下一个结点即可。

• 临界条件：待删除的结点时单链表的最后一个结点，这中情况只能通过遍历来操作了。

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 删除指定结点
*/
void deleteNode(Node* pHead, Node* pToBeDeleted) {
    if(pToBeDeleted == NULL) return;
    
    // pToBeDeleted不是最后一个结点
    if(pToBeDeleted->next) {
        pToBeDeleted->data = pToBeDeleted->next->data;
        Node* temp = pToBeDeleted->next;
        pToBeDeleted->next = pToBeDeleted->next->next;
        free(temp);
    }else {                              // pToBeDeleted是最后一个结点
        if(pHead == pToBeDeleted) {      // 链表中只有一个结点的情况
            pHead == NULL;
        }else {                          // 链表中有多个结点,pToBeDeleted是最后一个结点
            Node* p = pHead;
            while(p->next != pToBeDeleted) p = p->next;
            p->next = NULL;
            free(pToBeDeleted);
        }
    }
}

题目11：题目：线性表以带表头结点的循环单链表表示。设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。

基本思路：

• 取p，q两个指针，q 在 p之前，q 随 p 一起向后移动；

• 当k在循环单链表长度范围内时，使用传统的添加结点的方式；

• 当k超出循环单链表的长度时，表示 p 已经等于head了，那么q是最后一个结点，直接在q后面添加结点即可。

/**
* 题目：线性表以带表头结点的循环单链表表示。设计一个算法，
* 在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。
*/

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 在第k个元素前插入y
*/
void insert(Node* head, int k, int y) {
	Node* p = head->next;              // p指向首元结点 
	Node* q = head;                    // q指向头结点 

	int step = 1;                      // 初始化步数为1 
	while(step < k) {
		p = p->next;
		q = q->next;

		step++;                        // 这里的step一定要加1,注意！！！ 

		if(p == head) {                // 当超过循环单链表长度的时候就退出 
			break;
		}
	}

	Node* node = (Node*)malloc(sizeof(Node));
	node->data = y;

	if(p != head) {                    // 在循环单链表长度范围内 
		q->next = node;
		node->next = p;
	} else {                           // 超出循环单链表长度范围 
		q->next = node;
		node->next = head;
	}
}

题目12：删除单链表中值相同的多余结点。

基本思路：

• 创建指针p，用于遍历单链表；

• 创建指针q，q遍历p后面的结点，并与p的值作比较；

• 创建指针r，r保存需要删除的结点。

/**
* 题目：删除单链表中值相同的多余结点
*/

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 删除相同的多余结点
*/
void deleteOtherNode(Node* head) {
    // 单链不存在 或 只有一个结点直接退出
    if(head == NULL || head->next == NULL) {
        return;
    }
    Node* p = head;                            // p用于保存结点的值 
	Node* q;                                   // q用于遍历p之后的结点 
	while(p != NULL) {
		q = p;
		while(q->next != NULL) {
			if(q->next->data == p->data) {     // 相等就删除 
				Node* r = q->next;
				q->next = r->next;
				free(r);
			} else {                           // 不相等就继续遍历(重点逻辑) 
				q = q->next;
			}
		}

		p = p->next;
	}
}

题目13：将两个递增的有序单链表合并为一个递增的有序单链表。要求结果链表仍使用原来两个链表的存储空间，不占用其他存储空间。表中不允许有重复数据.。

基本思路：

• 合并后新表的使用头指针head指向，current为新表的工作指针，head1、head2分别为L1、L2的工作指针；

• 若有任意一个单链表为空就返回另一个单链表的头指针；

• 对新表的头指针进行初始化。如果取head1、head2中较小的值赋值给head并且head1(head2)先后移动一位；如果head1和head2相等，取head1并且head1、head2都向后移动一位；

• 遍历L1、L2，直到有一条单链表为空，赋值方法同上。

• 拼接单链表的剩余部分。

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 单链表的合并(不使用额外的存储空间且数据不重复) 
*/
Node* merge(Node* head1, Node* head2) {
	
	// 1.有任意一个单链表为空都返回另一个 
	if(head1 == NULL) return head2;
	if(head2 == NULL) return head1;

	// 2.为新单链表的头指针赋值 
	Node* head;
	if(head1->data < head2->data) {
		head = head1;
		head1 = head1->next;
	} else if(head1->data > head2->data) {
		head = head2;
		head2 = head2->next;
	} else {
		head = head1;
		head1 = head1->next;
		head2 = head2->next;                // 不会保留重复的结点(重点语句)
	}
	
	// 3.遍历两条单链表的公共部分添加到新的链表表
	Node* current = head;
	while(head1 != NULL && head2 != NULL) {
		if(head1->data < head2->data) {
			current->next = head1;
			current = head1;
			head1 = head1->next;
		} else if(head1->data > head2->data) {
			current->next = head2;
			current = head2;
			head2 = head2->next;
		} else {
			current->next = head1;
			current = head1;
			head1 = head1->next;
			head2 = head2->next;           // 不会保留重复的结点(重点语句)
		}
	}
	
	// 4.拼接单链表剩余的部分 
	if(head1 != NULL) current->next = head1;
	if(head2 != NULL) current->next = head2;
	
	return head;
}

单链表带有头结点的算法：

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 两个递增单链表合并为一个递增有序单链表
* 原链表和新链表均带有头结点
*/
Node* merge(Node* list1, Node* list2) {

	// 1.有任意一个单链表无有效数据就返回另一个单链表的头结点
	if(list1->next == NULL) return list2;
	if(list2->next == NULL) return list1;

	// 2.初始化新链表(为新链表创建头结点)
	Node* newList = (Node*)malloc(sizeof(Node));
	newList->next = NULL;

	Node* p = list1->next;              // p为list1的工作指针
	Node* q = list2->next;              // q为list2的工作指针
	Node* r = newList;                  // r为newList的工作指针

    // 3.在新链表中添加元素
	while(p != NULL && q != NULL) {
		if(p->data < q->data) {         // P小于q
			r->next = p;
			r = p;
			p = p->next;
		} else if(p->data > q->data) {  // p大于q
			r->next = q;
			r = q;
			q = q->next;
		} else {                        // p等于q
			r->next = p;
			r = p;
			p = p->next;
			
			// 释放list2中和list1值相同的结点 
			Node* temp = q;
			q = q->next;
			free(temp);
		}
	}

	if(p != NULL) r->next = p;
	if(q != NULL) r->next = q;

	return newList;
}

题目14：通过一趟遍历在单链表中找到最大结点。

/**
* 题目：通过一趟遍历在单链表中找到最大结点 
*/ 

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 通过一趟遍历找到单链表中最大的结点 
*/
Node* getMaxNode(Node* head) {
	
	// 1.单链表为空或只有一个结点,直接返回head即可 
	if(head == NULL || head->next == NULL) {
		return head;
	}
	
	// 2.对单链表进行遍历 
	Node* p = head;
	Node* max = p;
	while(p != NULL) {
		if(p->data > max->data) {
			max = p;
		}
		p = p->next;
	}
	
	return max;
}

题目15：设计一个算法，删除递增有序链表中大于mink且小于maxk的所有元素(mink和maxk是给定的两个参数，其值可以和表中元素相同，也可以不同)。

基本思路：

• 指针p初始化为单链表的头结点，只要p->next->data <= mink就向后移动，循环结束后p的位置为要删除的位置；

• 定义指针q=p->next，r=q->next，释放q，将r赋值给q，只要r->data < maxk就向后移动，循环结束后r的位置为删除结束的位置；

• 将p->next=r，连接单链表，删除操作完成。

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 删除表中元素(单链表带头结点)
*/
void deleteNode(Node* head, int mink, int maxk) {
	
	// 1.指针p初始化为头结点 
	Node* p = head;         
	
	// 2.当p->next->data <= mink就向后移动   
	while(p->next != NULL && p->next->data <= mink) {
		p = p->next;
	}

	// 3.指针q待删除结点 
	Node* q = p->next;
	Node* r = q->next;
	
	// 4.结点删除后,只要r->data < maxk就继续向后移动 
	while(r != NULL && r->data < maxk) {
		free(q);
		q = r;
		r = r->next;
	}
	
	// 5.结点全部删除后连接p和r 
	p->next = r;
}

题目16：对单链表进行冒泡排序。

/**
* 题目：对单链表进行冒泡排序
*/

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 单链表的冒泡排序 
*/
void sort(Node* head) {

	// 单链表不存在 或 只有一个结点 
	if(head == NULL || head->next == NULL) return;

	Node* p;
	Node* q;
	// 冒泡排序的趟数(n-1)
	for(p = head; p->next != NULL; p = p->next) {
		for(q = p->next; q != NULL; q = q->next) {
			// 比较(两两进行比较) 交换的是数据域中的值
			if(p->data > q->data) {
				int temp = p->data;
				p->data = q->data;
				q->data = temp;
			}
		}
	}
}

题目17：将一个数据域为整数的单链表分割为两个分别为奇数和偶数的链表。

基本思路：单链表设置头结点。在原链表进行操作，依次扫描判断，如果为偶数，就把它移动到另一个链表。

/**
* 定义结点
*/
typedef struct _node {
	int data;
	struct _node* next;
} Node;

/**
* 将单链表拆分为奇链和偶链(带有头结点)
* 思路：若结点是偶数就将其移动到另一个链表
*/
Node* split(Node* head) {

	// 单链表中没有元素 
	if(head->next == NULL) return NULL;

	// 初始化偶数链(创建头结点)
	Node* linkEven = (Node*)malloc(sizeof(Node));
	linkEven->next = NULL;

	Node* p = head;                    // 原链的工作指针
	Node* q = linkEven;                // 偶链的工作指针

	while(p->next != NULL) {
		Node* temp = p->next;
		if(temp->data % 2 == 0) {
			// 偶数,从原链上释放,添加到偶链中
			p->next = temp->next;
			q->next = temp;
			q = temp;
			q->next = NULL;
		} else {
			p = p->next;
		}
	}
	return linkEven;
}