C语言中的单链表面试题----基础

题目总览

从尾到头打印单链表删除一个无头单链表的非尾节点在无头单链表的一个节点前插入一个节点单链表实现约瑟夫环逆置/反转单链表单链表排序（冒泡排序&快速排序）合并两个有序链表,合并后依然有序查找单链表的中间节点，要求只能遍历一次链表查找单链表的倒数第n个节点，要求只能遍历一次链表

思路及代码

从尾到头打印单链表

递归法，若当前节点不为空，在打印当前节点前打印上一个节点。

void ConversePrint(ListNode* pList) { if (pList != NULL) { ConversePrint(pList->next); printf("%d ", pList->data); } } 12345678 12345678

删除一个无头单链表的非尾节点

将当前节点的内容改为下个节点的内容，释放下个节点，让当前节点指向下下个节点。

void popNode(ListNode* pList) { if (pList != NULL) { ListNode* tmp = pList->next; pList->data = pList->next->data; pList->next = pList->next->next; free(tmp); } } 12345678910 12345678910

在无头单链表的一个节点前插入一个节点

新建一个节点保存当前节点的内容，并指向下一个节点。  将当前节点改为插入的内容，指向新节点。

void InsertBefore(ListNode* pList, DataType x) { assert(pList); ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = pList->data; newNode->next = pList->next; pList->next = newNode; pList->data = x; } 123456789 123456789

单链表实现约瑟夫环

接收一个环形链表的头指针地址，将头指针改为剩下的最后一个节点。处理空链表。用一个节点指针指向头节点，当前节点的下一节点不是当前节点（节点数大于一），循环，当前节点为第一个节点，走 n-1 步，指向第n个节点，删除当前节点。将初始头指针赋值最后节点。 void Joseph(ListNode** ppList, int n) { assert(ppList); if (*ppList == NULL)return; ListNode* pList = *ppList; while (pList->next != pList) { int i; for (i = 1; i < n; i++) pList = pList->next; popNode(pList); } *ppList = pList; } 1234567891011121314 1234567891011121314

逆置/反转单链表

头插法，建立新链表，用 cur 指向旧链表头结点。循环，用 tmp 保存要拿下来的原链表头结点 cur， cur 指向下一节点，将 tmp 放到新链表的头部（tmp的下一节点指向新链表头结点，再将新链表的头结点改为 tmp），直到 cur 为 NULL。将原链表头指针改为新链表。 void ReverseList(ListNode** ppList) { assert(ppList); ListNode* newList = NULL; ListNode* cur = *ppList; while (cur) { ListNode* tmp = cur; cur = cur->next; tmp->next = newList; newList = tmp; } *ppList = newList; } 123456789101112131415 123456789101112131415

单链表排序（冒泡排序）

接收一个普通单链表，处理空链表和只有一个节点的情况。用 tail 指示一次冒泡的终点，第一次要全排，赋值为NULL。循环冒泡比较，每次比较（交换）后，cur 和 next 都指向它们的下一个节点，直到 next == tail。交换中，修改交换标记 exchange。外层循环，用 cur 表示比较的第一个节点，用 next 表示比较的下一个节点，exchange 记录是否交换，一趟比较没有交换，说明已排好，直接返回。每趟比较之后，此次最后一个值已经为最大，tail 前移一个节点。 void ListBubbleSort(ListNode* pList) { if (pList == NULL || pList->next == NULL)return; ListNode* tail = NULL; while (tail != pList) { ListNode* cur = pList; ListNode* next = pList->next; int exchange = 0; while (next != tail) { if (cur->data > next->data) { DataType num = cur->data; cur->data = next->data; next->data = num; exchange = 1; } cur = next; next = next->next; } if (exchange == 0) return; tail = cur; } } 123456789101112131415161718192021222324252627 123456789101112131415161718192021222324252627

合并两个有序链表,合并后依然有序

方法一  - 新链表段接法  - 接收两个链表指针，处理有空链表的情况。  - 创建新链表头指针，指向两链表头节内值点较小的的节点。  - 循环，节点小的指针后移，直到节点下一节点大于另一指针或节点为空，tmp 保存下一节点，当前节点指向另一指针，当前指针赋值为 tmp，如果当前指针为 NULL，说明合并完成，结束循环。  - 返回新链表头指针。  - 可以总是让 p1 指向小的，p2 指向大的，循环挪 p1，接完后再把小的给 p1，大的给 p2。可以不用比较。（原方法 else 是复制 if 后，1 和 2 换，其实更简单，看起来多）  思路图 

ListNode* MergeList(ListNode* List1, ListNode* List2) { if (List1 == NULL)return List2; if (List2 == NULL)return List1; ListNode* newList = List1->data <= List2->data ? List1 : List2; while (true) { if(List1->data <= List2->data) { while (List1->next != NULL && List1->next->data <= List2->data) { List1 = List1->next; } ListNode* tmp = List1->next; List1->next = List2; List1 = tmp; if (List1 == NULL) break; } else { while (List2->next != NULL && List2->next->data <= List1->data) { List2 = List2->next; } ListNode* tmp = List2->next; List2->next = List1; List2 = tmp; if (List2 == NULL) break; } } return newList; } 1234567891011121314151617181920212223242526272829303132333435 1234567891011121314151617181920212223242526272829303132333435

方法二  - 新链单节点表尾插法  - 新建 newList = NULL, 循环，每次比较两指针内容，保存小的节点，小节点指针后移，小节点尾接到 newList。  - 如果有一个指针为 NULL，另一个指针尾接到 newList，返回 newList。  方法三  - 介于上两个方法之间，以头结点小的为 newList，另一个链表每次拿下一个节点接到 newList 的合适位置，直到其中一个指针为空。

查找单链表的中间节点，要求只能遍历一次链表

快慢指针法，初始快指针、慢指针都是头指针。循环，如果快指针能走两步（快指针的下一个节点和下下一个节点不为空），快指针走两步，慢指针走一步。返回慢指针。 ListNode* FindMidNode(ListNode* pList)//mid = total>>1 { ListNode* fast = pList; while (fast->next != NULL && fast->next->next != NULL) { fast = fast->next->next; pList = pList->next; } return pList; } 12345678910 12345678910

查找单链表的倒数第n个节点，要求只能遍历一次链表

当节点数少于n时，NULL。快慢指针法，创建返回指针 ret ，快指针先走 n-1 步（此时 ret 为快指针的倒数第 n 个节点）或到 NULL 为止。循环，快指针的下一个节点不为空，快指针和 ret 都向后走一步。返回返回指针。 ListNode* FindFromLast(ListNode* pList, int n) { ListNode* ret = pList; while (--n) { if(ret == NULL)return NULL; pList = pList->next; } while (pList->next != NULL) { ret = ret->next; pList = pList->next; } return ret; }