連結清單常見面試題

“link.h”

#ifndef __LINK_LIST_H__

#define __LINK_LIST_H__

#include <stdio.h>

#include <assert.h>

#include <stdlib.h>

#include <malloc.h>

typedef int DataType;

typedef struct LinkNode

{

DataType data;

struct LinkNode *next;

}LinkNode,*pLinkNode,*pList;

void InitLinkList(pList* pHead);

//void Destroy(pList *pHead);

void PushBack(pList* pHead, DataType x);

void PrintList(pList list);

pLinkNode Find(pList head, DataType x);

void EraseNotTail(pLinkNode pos);//删除無頭單連結清單的非尾節點

void ReverseList(pList* pHead);//反轉（逆序）連結清單--2

void BubbleSort(pList * pHead);//排序連結清單（冒泡）--3

void InsertFrontNode(pLinkNode pos, DataType x);// 在目前節點前插入一個資料x-----5

pLinkNode Merge(pList l1, pList l2);//合并兩個有序清單-----6

pLinkNode FindMidNode(pList head);//查找連結清單的中間節點---7

void InitLinkList(pList* pHead)//初始化

assert(pHead);

*pHead = NULL;

}

pLinkNode buyNode(DataType x)//構造節點

pLinkNode newNode = (pLinkNode)malloc(sizeof(LinkNode));

newNode->data = x;

newNode->next = NULL;

return newNode;

void PushBack(pList* pHead, DataType x)//尾插

pLinkNode newNode;

pLinkNode cur = *pHead;

newNode = buyNode(x);

if(*pHead == NULL)

{

*pHead = newNode;

return;

}

else

while(cur->next)

{

cur = cur->next;

}

cur->next = newNode;

pLinkNode Find(pList head, DataType x)//查找某一節點

pLinkNode cur = head;

if(head == NULL)

printf("連結清單中無節點\n");

else 

while(cur)

if(cur->data == x)

return cur;

return NULL;

void PrintList(pList list)//列印

pList cur = list;

while(cur)

printf("%d ",cur->data);

cur = cur->next;

printf("over");

void EraseNotTail(pLinkNode pos)

DataType x;

pLinkNode del = NULL;

    x = pos->data;

pos->data = pos->next->data;

pos->next->data = x;

del = pos->next;

pos->next = del->next;

free(del);

del = NULL;

void ReverseList(pList* pHead)//逆序

pLinkNode prev = NULL;

pLinkNode newHead = NULL;

if(cur == NULL)

if(cur->next == NULL)

prev = cur;

prev->next = newHead;

newHead = prev;

*pHead = newHead;

void BubbleSort(pList * pHead)//排序連結清單（冒泡）--3

pLinkNode end = NULL;

while(cur != end)

while(cur&&cur->next!=end)

if(cur->data > cur->next->data)

{

x = cur->data;

cur->data = cur->next->data;

cur->next->data = x;

}

end = cur;

cur = *pHead;

void InsertFrontNode(pLinkNode pos, DataType x)// 在目前節點前插入一個資料x-----5

pLinkNode newNode = buyNode(x);

DataType tmp;

assert(pos);

newNode->next = pos->next;

pos->next = newNode;

tmp = pos->data;

pos->data = newNode->data;

newNode->data = tmp;

pLinkNode Merge(pList l1, pList l2)//合并兩個有序清單-----6

pList newHead = NULL;

pLinkNode cur = newHead;

if(l1 == l2)

return l1;

if(l1 == NULL && l2 != NULL)

return l2;

if(l1 !=NULL && l2 == NULL)

if(l1->data < l2->data)

newHead = l1;

l1 = l1->next;

newHead = l2;

l2 = l2->next;

cur = newHead;

while(l1&&l2)

if(l1->data<l2->data)

cur->next = l1;

l1 = l1->next;

else

cur->next = l2;

l2 = l2->next;

if(l1)

cur->next = l1;

cur->next = l2;

return newHead;

pLinkNode FindMidNode(pList head)//查找連結清單的中間節點---7

pLinkNode mid = head;

return NULL;

while(cur->next)

cur = cur->next->next;

mid = mid->next;

return mid;

#endif //__LINK_LIST_H__

“test.c”

#include "link.h"

void Test1()

pList mylist;

pLinkNode ret = NULL;

InitLinkList(&mylist);

PushBack(&mylist,1);

PushBack(&mylist,2);

    PushBack(&mylist,3);

    PushBack(&mylist,4);

    PushBack(&mylist,5);

ret = Find(mylist,2);

EraseNotTail(ret);

PrintList(mylist);

void Test2()

PushBack(&mylist,4);

    PushBack(&mylist,2);

BubbleSort(&mylist);

void Test3()

ret = Find(mylist,4);

    InsertFrontNode(ret,6);

void Test4()

ret = FindMidNode(mylist);

if(ret != NULL)

printf("%d ",ret->data);

void Test5()

pList l1;

pList l2;

pList ret = NULL;

InitLinkList(&l1);

InitLinkList(&l2);

PushBack(&l1,1);

PushBack(&l1,3);

PushBack(&l1,5);

PushBack(&l2,2);

PushBack(&l2,4);

PushBack(&l2,6);

ret = Merge(l1,l2);

PrintList(ret);

void Test6()

//PrintList(mylist);

ReverseList(&mylist);

int main()

Test6();