单链表及相关面试题

//SlistNode.h #pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <Windows.h> #include <assert.h> typedef int Datatype; typedef struct SlistNode { Datatype data; struct SlistNode* next; }SlistNode; void InitSlist(SlistNode*& pHead); void PrintList(SlistNode*& pHead); void PushBack(SlistNode*& pHead,Datatype a); void PopBack(SlistNode*& pHead); void PushFront(SlistNode*& pHead, Datatype a); void PopFront(SlistNode*& pHead); void Insert(SlistNode*& pHead, SlistNode*& pos, Datatype a); void Erase(SlistNode*& pHead, SlistNode*& pos); void Remove(SlistNode*& pHead,Datatype a); SlistNode* Find(SlistNode* pHead, Datatype a); void Destory(SlistNode*& pHead); SlistNode* BuyNode(Datatype a); /////////单链表有关面试题//////////// void PrintListFromT2H(SlistNode* pHead); void ReverseList(SlistNode*& pHead);//逆置/反转单链表 //删除一个无头单链表的非尾节点 void DeleteNotpHead(SlistNode* pos); //在无头单链表的一个非头节点前插入一个节点 void InsertNotpHead(SlistNode* pos, Datatype a); //单链表实现约瑟夫环 SlistNode* JosephCircle(SlistNode* pHead, int k); //冒泡排序 void BubbleSort(SlistNode* pHead); //合并两个有序链表合并后依然有序 SlistNode* Merge(SlistNode* pHead1, SlistNode* pHead2); //查找单链表的中间节点，要求只遍历一次链表 SlistNode* FindMiddleNode(SlistNode* pHead); //查找单链表中倒数第k个节点，要求只遍历一次 SlistNode* FindNode(SlistNode* pHead,int k); //判断单链表是否带环，若带环，求环的长度 SlistNode* IsCircle(SlistNode* pHead); size_t CircleLength(SlistNode* pHead); //求环的入口点 SlistNode* CircleEntry(SlistNode* pHead); //判断两个链表是否相交，求交点 SlistNode* GetMeetNode(SlistNode* pHead1, SlistNode* pHead2); //求两个已排序单链表中的相同数据 void UnionSet(SlistNode* list1, SlistNode* list2); //SlistNode.c #include "SlistNode.h" void InitSlist(SlistNode*& pHead) { pHead = NULL; } void PrintList(SlistNode*& pHead) { SlistNode* temp = pHead; if (temp == NULL) { return; } while (temp) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } SlistNode* BuyNode(Datatype a) { SlistNode* node = (SlistNode*)malloc(sizeof(SlistNode)); assert(node); node->data = a; node->next = NULL; return node; } void PushBack(SlistNode*& pHead, Datatype a) { if (pHead == NULL) { pHead = BuyNode(a); } else { SlistNode* pcur = pHead; while (pcur->next) { pcur = pcur->next; } pcur->next = BuyNode(a); } } void PopBack(SlistNode*& pHead) { assert(pHead); if (pHead->next == NULL) { free(pHead); pHead = NULL; } else { SlistNode* pcur = pHead; SlistNode* pre = pcur; while (pcur->next) { pre = pcur; pcur = pcur->next; } free(pcur); pcur = NULL; pre->next = NULL; } } void PushFront(SlistNode*& pHead, Datatype a) { assert(pHead); if (pHead == NULL) { pHead = BuyNode(a); } else { SlistNode* newnode = BuyNode(a); newnode->next = pHead; pHead = newnode; } } void PopFront(SlistNode*& pHead) { assert(pHead); if (pHead == NULL) { return; } else if (pHead->next==NULL) { free(pHead); pHead = NULL; } else { SlistNode* pcur = pHead; pHead = pHead->next; free(pcur); pcur = NULL; } } void Insert(SlistNode*& pHead, SlistNode*& pos, Datatype a)//在pos之前插入数据 { assert(pHead); assert(pos); if (pHead == pos) { SlistNode* newnode = BuyNode(a); newnode->next = pHead; pHead = newnode; } else { SlistNode* pcur = pHead; SlistNode* pre = pcur; while (pcur != pos) { pre = pcur; pcur = pcur->next; } SlistNode* newnode = BuyNode(a); newnode->next = pcur; pre->next = newnode; } } SlistNode* Find(SlistNode* pHead, Datatype a) { assert(pHead); SlistNode* temp = pHead; while (temp) { if (temp->data == a) { return temp; } temp = temp->next; } return NULL; } void Erase(SlistNode*& pHead, SlistNode*& pos) { assert(pHead&&pos); if (pos == pHead) { SlistNode* temp = pHead; pHead = pHead->next; free(temp); temp = NULL; } else { SlistNode* pcur = pHead; while (pcur->next != pos) { pcur = pcur->next; } pcur->next = pos->next; free(pos); pos = NULL; } } void Remove(SlistNode*& pHead, Datatype a) { assert(pHead); SlistNode* pos = Find(pHead, a); if (pos == pHead) { SlistNode* temp = pHead; pHead = pHead->next; free(temp); temp = NULL; } else { SlistNode* pcur = pHead; while (pcur->next != pos) { pcur = pcur->next; } pcur->next = pos->next; free(pos); pos = NULL; } } void Destory(SlistNode*& pHead) { assert(pHead); free(pHead); pHead = NULL; } void PrintListFromT2H(SlistNode* pHead)//从尾到头打印 { if (pHead) { PrintListFromT2H(pHead->next); printf("%d ", pHead->data); } } void ReverseList(SlistNode*& pHead)//逆置/反转单链表 { assert(pHead); SlistNode* newhead = NULL; SlistNode* pcur = pHead; while (pcur) { SlistNode*temp = pcur;//摘节点 pcur = pcur->next; temp->next = newhead;//头插 newhead = temp; } pHead = newhead; } void DeleteNotpHead(SlistNode*pos) { assert(pos); SlistNode* next = pos->next; pos->data = next->data; pos->next = next->next; free(next); } void InsertNotpHead(SlistNode* pos, Datatype a) { assert(pos); SlistNode* newnode = BuyNode(pos->data); SlistNode* next = pos->next; pos->next = newnode; newnode->next = next; pos->data = a; } SlistNode* JosephCircle(SlistNode* pHead, int k) { SlistNode* pcur = pHead; while (pcur->next != pcur) { int x = k; while (--x) { pcur = pcur->next; } SlistNode* next = pcur->next; pcur->data = next->data; pcur->next = next->next; free(next); } return pcur; } void BubbleSort(SlistNode* pHead) { if (pHead == NULL&&pHead->next == NULL) { return; } else { SlistNode* tail = NULL; int flag = 1; while (tail != pHead->next) { SlistNode* pcur = pHead; SlistNode* pnext = pcur->next; do { if (pcur->data > pnext->data) { Datatype ret = pcur->data; pcur->data = pnext->data; pnext->data = ret; flag = 0; } pcur = pcur->next; pnext = pnext->next; }while (pnext!= tail); if (flag == 1) { return; } tail = pcur; } } } SlistNode* Merge(SlistNode* pHead1, SlistNode* pHead2) { if (pHead1==NULL) { return pHead2; } else if (pHead2==NULL) { return pHead1; } else { SlistNode* newhead ,*tail; SlistNode* l1 = pHead1; SlistNode* l2 = pHead2; if (l1->data > l2->data) { newhead = tail = l2; } else { newhead = tail = l1; } while (l1!=NULL && l2!=NULL) { SlistNode* temp ; if (l1->data < l2->data) { temp = l1; l1 = l1->next; } else { temp = l2; l2 = l2->next; } tail->next = temp; tail=temp; } if (l2) { tail->next = l2; } if (l1) { tail->next = l1; } return newhead; } } SlistNode* FindMiddleNode(SlistNode* pHead) { assert(pHead); SlistNode* fast = pHead; SlistNode* slow = pHead; while (fast&&fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } SlistNode* FindNode(SlistNode* pHead,int k) { assert(pHead); SlistNode* fast = pHead; SlistNode* slow = pHead; while (k--) { fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } return slow; } SlistNode*IsCircle(SlistNode* pHead) { assert(pHead); SlistNode* fast = pHead; SlistNode* slow = pHead; while (fast &&fast->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return slow; } } return NULL; } size_t CircleLength(SlistNode* pHead) { assert(pHead); int count = 1; SlistNode* meet = IsCircle(pHead); SlistNode* pcur = meet->next; while (pcur != meet) { pcur = pcur->next; count++; } return count; } SlistNode* CircleEntry(SlistNode* pHead) { assert(pHead); SlistNode* meet = IsCircle(pHead); SlistNode* pcur = pHead; while (pcur != meet) { pcur = pcur->next; meet = meet->next; } return pcur; } SlistNode* GetMeetNode(SlistNode* pHead1, SlistNode* pHead2)//不带环 { assert(pHead1); assert(pHead2); SlistNode* pcur1 = pHead1; SlistNode* pcur2 = pHead2; int len1 = 0; int len2 = 0; while (pcur1) { pcur1 = pcur1->next; len1++; } while (pcur2) { pcur2 = pcur2->next; len2++; } int k = abs(pcur1 - pcur2); SlistNode* longlist,*shortlist; if (len1 > len2) { longlist = pHead1; shortlist = pHead2; } else { longlist = pHead2; shortlist = pHead1; } while (k--) { longlist = longlist->next; } while (longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } return shortlist; } void UnionSet(SlistNode* list1, SlistNode* list2) { assert(list1); assert(list2); while (list1&&list2) { if (list1->data > list2->data) { list2 = list2->next; } else if (list1->data < list2->data) { list1 = list1->next; } else { printf("%d ", list1->data); list1 = list1->next; list2 = list2->next; } } printf("\n"); } //test.c #define _CRT_SECURE_NO_WARNINGS 1 #include "SlistNode.h" void test1() { SlistNode* Node; InitSlist(Node); PushBack(Node, 1); PushBack(Node, 2); PushBack(Node, 3); //PrintList(Node); //PopBack(Node); //PopBack(Node); //PushFront(Node, 4); //PushFront(Node, 5); //PrintList(Node); //PopFront(Node); //PopFront(Node); // PrintList(Node); //SlistNode* pos1 = Find(Node, 4); //Insert(Node, pos1, 0);//在pos之前插入数据 //PrintList(Node); //SlistNode* pos2 = Find(Node, 5); // Erase(Node, pos2); //Remove(Node, 1); //ReverseList(Node);//逆置/反转单链表 // PrintList(Node); //PrintListFromT2H(Node);//从尾到头打印 //printf("\n"); //Destory(Node); } void test2() { SlistNode* Node; InitSlist(Node); PushBack(Node, 1); PushBack(Node, 2); PushBack(Node, 3); PushBack(Node, 7); PushBack(Node, 5); PrintList(Node); //Remove(Node, 1); SlistNode* pos = Find(Node, 5); //InsertNotpHead(pos, 0); pos->next = Node; SlistNode* ret = JosephCircle(Node, 3); printf("%d\n", ret->data); //PrintList(Node); /*SlistNode* pos = Find(Node, 1); DeleteNotpHead(pos); PrintList(Node);*/ } void test3() { SlistNode* Node1; InitSlist(Node1); PushBack(Node1, 1); PushBack(Node1, 3); PushBack(Node1, 4); PushBack(Node1, 5); PushBack(Node1, 7); PushBack(Node1, 8); PrintList(Node1); //SlistNode* ret = FindMiddleNode(Node1); SlistNode* ret = FindNode(Node1, 1); printf("%d\n", ret->data); //SlistNode* Node2; //InitSlist(Node2); //PushBack(Node2, 2); //PushBack(Node2, 4); //PushBack(Node2, 6); //PushBack(Node2, 8); //PushBack(Node2, 8); //PrintList(Node2); //SlistNode* Node=Merge(Node1, Node2); BubbleSort(Node); //PrintList(Node); } void test4() { SlistNode* Node1; InitSlist(Node1); PushBack(Node1, 1); PushBack(Node1, 3); PushBack(Node1, 4); PushBack(Node1, 6); PushBack(Node1, 7); PrintList(Node1); SlistNode* Node2; InitSlist(Node2); PushBack(Node2, 1); PushBack(Node2, 4); PushBack(Node2, 6); PushBack(Node2, 8); PushBack(Node2, 9); PrintList(Node2); UnionSet(Node1, Node2); /*SlistNode* ret = Find(Node1, 4); SlistNode* tail = Find(Node1, 7); tail->next = ret; SlistNode*meet= GetMeetNode(Node1,Node2); printf("%d", meet->data);*/ //SlistNode* ret = Find(Node1, 3); //SlistNode* tail = Find(Node1, 7); //tail->next = ret; //SlistNode* pos = IsCircle(Node1); //printf("%d\n", pos->data); //size_t length = CircleLength(Node1); //printf("%u\n", length); //SlistNode* entry = CircleEntry(Node1); //printf("%d\n", entry->data); } int main() { //test1(); //test2(); //test3(); test4(); system("pause"); return 0; }