단일 링크 흔 한 면접 문제

//LinkList.h
#ifndef _LINKLIST_H__
#define _LINKLIST_H__

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node* next;
}Node,*pNode,*pList;
void InitList(pList* pplist);
//   
void PushBack(pList* pplist);
//  
void BubbleSort(pList* pplist);
//       
void ReversePrint(pList plist);
//             
void EraseNotTail(pNode pos);
//                   
void InsertFrontNode(pNode pos, DataType x);
//       
void JosephCycle(pList* pplist, int k);
//       
void ReverseList(pList* pplist);
//         
pList Merge(const pList* p1, const pList* p2);
//          ,           
pNode FindMidNode(pList plist);
//         k   ,           
pNode FindKNode(pList plist, int k);
//         
pNode CheckCircle(pList plist);
//      
int GetCircleLength(pNode meet);
//       
pNode GetCycleEntryNode(pList plist, pNode meet);
//             
int CheckCross(pList list1, pList list2);
//    
pNode GetCrossNode(pList list1, pList list2);
#endif


//LinkList.c
#define _CRT_SECURE_NO_WARNINGS
#include"LinkList.h"
pNode buynode(DataType x)
{
    pNode tmp = NULL;
    tmp = (pNode)malloc(sizeof(Node));
    if (tmp == NULL)
    {
        perror("malloc");
        exit(1);
    }
    tmp->data = x;
    tmp->next = NULL;
    return tmp;
}
void InitList(pList* pplist)
{
    assert(pplist);
    *pplist = NULL;
}
//   
void PushBack(pList* pplist,DataType x)
{

    pNode cur = NULL;
    assert(pplist);
    cur = *pplist;
    pNode newnode = buynode(x);
    if (*pplist == NULL)
    {
        *pplist = newnode;
    }
    else
    {
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}
//  
void BubbleSort(pList* pplist)
{
    pNode cur = NULL;
    pNode tail = NULL;
    assert(pplist);
    cur = *pplist;
    if (*pplist == NULL)
    {
        return;
    }
    while (cur != tail)
    {
        while (cur->next!=tail)
        {
            if (cur->data < cur->next->data)
            {
                DataType tmp = cur->data;
                cur->data = cur->next->data;
                cur->next->data = tmp;
            }
            cur = cur->next;
        }
        tail = cur;
        cur = *pplist;
    }
}
//       
void Display(pList plist)
{
    pNode tmp = plist;
    while (tmp)
    {
        printf("%d->", tmp->data);
        tmp = tmp->next;
    }
    printf("end
"
); } // x pNode Find(pList pplist,DataType x) { pNode cur = pplist; if (pplist == NULL) { return NULL; } else { while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } } // void EraseNotTail(pNode pos) { pNode cur = NULL; assert(pos); cur = pos->next; pos->data = cur->data; pos->next = cur->next; free(cur); cur = NULL; } // void InsertFrontNode(pNode pos, DataType x) { pNode NewNode = NULL; assert(pos); NewNode = buynode(x); NewNode->next = pos->next; pos->next = NewNode; DataType tmp = pos->data; pos->data = NewNode->data; NewNode->data = tmp; } // void JosephCycle(pList* pplist, int k) { } // void ReverseList(pList* pplist) { pNode cur = *pplist; pNode p = NULL; pNode r = NULL; assert(pplist); while (cur) { r = p; p = cur; cur = cur->next; p->next = r; } *pplist = p; } // pList Merge(const pList* p1, const pList* p2) { pList newnode = NULL; pNode cur = NULL; pNode cur1 = *p1; pNode cur2 = *p2; assert(p1); assert(p2); //p1 p1 ( NULL) if (*p1 == *p2) { return *p1; } // , if ((*p1 == NULL) && (*p2 != NULL)) { return *p2; } if ((*p2 == NULL) && (*p1 != NULL)) { return *p1; } //2 if (cur1->data < cur2->data) { newnode = cur1; cur1 = cur1->next; newnode->next = NULL; } else { newnode = cur2; cur2 = cur2->next; newnode->next = NULL; } cur = newnode; while (cur1&&cur2) { if (cur1->data > cur2->data) { cur->next = cur2; cur2 = cur2->next; cur = cur->next; } else { cur->next = cur1; cur1 = cur1->next; cur = cur->next; } } if (cur1 == NULL) { cur->next = cur2; } else { cur->next = cur1; } return newnode; } // , pNode FindMidNode(pList plist) { pNode slow = plist; pNode fast = plist; if ((fast == NULL) || (fast->next == NULL)) { return fast; } else { while (fast&&fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } } // k , pNode FindKNode(pList plist, int k) { pNode fast = plist; pNode slow = plist; if (plist == NULL) { return NULL; } int i = 0; for (i; i < k-1; i++) { fast = fast->next; if (fast == NULL) { return NULL; } } fast = fast->next; while (fast) { fast = fast->next; slow = slow->next; } return slow; } // pNode CheckCircle(pList plist) { pNode slow = plist; pNode fast = plist; if (plist == NULL) { return NULL; } else { while (fast&&fast->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return slow; break; } } return NULL; } } // int GetCircleLength(pNode meet) { int count = 0; pNode cur = meet; do { count++; cur = cur->next; } while (cur!=meet); return count; } // pNode GetCycleEntryNode(pList plist, pNode meet) { } // int CheckCross(pList list1, pList list2) { pNode cur1 = list1; pNode cur2 = list2; if (cur1 == NULL || cur2 == NULL) { return 0; //0 ,1 } while (cur1->next) { cur1 = cur1->next; } while (cur2->next) { cur2 = cur2->next; } if (cur1 == cur2) { return 1; } return 0; } // pNode GetCrossNode(pList list1, pList list2) { int len1 = 0, len2 = 0; pNode cur1 = NULL; pNode cur2 = NULL; cur1 = list1; cur2 = list2; while (cur1->next) { len1++; cur1 = cur1->next; } while (cur2->next) { len2++; cur2 = cur2->next; } int diff = abs(len2 - len1); if (len1 > len2) { cur1 = list1; cur2 = list2; } else { cur1 = list2; cur2 = list1; } for (int i = 0; i < diff; i++) { cur1 = cur1->next; } while (cur1 != cur2) { cur1 = cur1->next; cur2 = cur2->next; } return cur1; } //test.c #define _CRT_SECURE_NO_WARNINGS #include"LinkList.h" void test1() { pList pplist; InitList(&pplist); PushBack(&pplist, 1); PushBack(&pplist, 2); PushBack(&pplist, 3); PushBack(&pplist, 4); Display(pplist); //ReversePrint1(&pplist); //ReversePrint2(&pplist); Display(pplist); } void test2() { pList pplist; pNode node = NULL; InitList(&pplist); PushBack(&pplist, 1); PushBack(&pplist, 2); PushBack(&pplist, 3); PushBack(&pplist, 4); Display(pplist); node = Find(pplist, 3); EraseNotTail(node); InsertFrontNode(node, 10); Display(pplist); } void test3() { pList pplist; pNode node = NULL; InitList(&pplist); PushBack(&pplist, 11); PushBack(&pplist, 2); PushBack(&pplist, 7); PushBack(&pplist, 4); Display(pplist); BubbleSort(&pplist); Display(pplist); } void test4() { pList s1; pList s2; pList s3 = NULL; pList node = NULL; pNode mid = NULL; InitList(&s1); InitList(&s2); PushBack(&s1, 1); PushBack(&s1, 3); PushBack(&s1, 5); Display(s1); PushBack(&s2, 2); PushBack(&s2, 4); PushBack(&s2, 6); PushBack(&s2, 8); PushBack(&s2, 10); Display(s2); node = Merge(&s2, &s1); mid=FindMidNode(node); Display(node); printf("%d
"
, mid->data); } void test5() { pList pplist; pNode node = NULL; InitList(&pplist); PushBack(&pplist, 11); PushBack(&pplist, 2); PushBack(&pplist, 7); PushBack(&pplist, 44); PushBack(&pplist, 5); PushBack(&pplist, 8); node= Find(pplist, 8); node->next = Find(pplist, 2); Display(pplist); node = FindKNode(pplist, 7); printf("%d
"
, node->data); } void test6() { pList pplist; pNode node = NULL; pNode newnode = NULL; InitList(&pplist); PushBack(&pplist, 11); PushBack(&pplist, 2); PushBack(&pplist, 7); PushBack(&pplist, 44); PushBack(&pplist, 5); PushBack(&pplist, 8); node = Find(pplist, 8); node->next = Find(pplist, 2); newnode = CheckCircle(pplist); //printf("%d
", newnode->data);
int ret=GetCircleLength(newnode); printf("%d
"
, ret); } void test7() { pList s1; pList s2; pNode node; pNode c; InitList(&s1); InitList(&s2); PushBack(&s1, 1); PushBack(&s1, 3); PushBack(&s1, 5); PushBack(&s2, 2); PushBack(&s2, 4); PushBack(&s2, 6); PushBack(&s2, 8); PushBack(&s2, 10); node = Find(s1, 5); node->next = Find(s2, 6); int ret = CheckCross(NULL, NULL); if (ret == 1) { printf("
"
); } else { printf("
"
); } c = GetCrossNode(s1, s2); printf("%d
"
, c->data); } int main() { //test1(); //test2(); //test3(); //test4(); //test5(); //test6(); test7(); system("pause"); return 0; }

좋은 웹페이지 즐겨찾기