0

尝试了链表问题1.来自Cracking the coding interview here in cpp。-编写代码以从未排序的链表中删除重复项。跟进 如果不允许使用临时缓冲区，您将如何解决这个问题？

你觉得这个实现怎么样。

#include "stdafx.h"
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head = (node*)malloc(sizeof(node));
struct node *tail = (node*)malloc(sizeof(node));

struct node* createNode(int data)
{
    struct node *newNode = (node*)malloc(sizeof(node));
    newNode->data = data;
    newNode->next = NULL;
    head = newNode;
    return newNode;
}

bool insertAfter(node * list, int data)
{
    //case 1 - insert after head
    struct node *newNode = (node*)malloc(sizeof(node));
    if (!list)
    {

        newNode->data = data;
        newNode->next = head;
        head = newNode;
        return true;
    }

    struct node * curpos = (node *)malloc(sizeof(node));
    curpos = head;
    //case 2- middle, tail of list
    while (curpos)
    {
        if (curpos == list)
        {
            newNode->data = data;
            if (curpos->next == NULL)
            {
                newNode->next = NULL;
                tail = newNode;
            }
            else
            {
                newNode->next = curpos->next;
            }
            curpos->next = newNode;
            return true;
        }
        curpos = curpos->next;
    }
}

void deleteNode(node *runner, node * curr){

    //DELETE AT TAIL
    if (runner->next->next == NULL)
    {
        runner->next = NULL;        
    }
    else//delete at middle
    {
        runner->next = runner->next->next;
    }
}


void removedups(node * list)
{
    struct node * curr = (node*)malloc(sizeof(node));
    struct node * runner = (node*)malloc(sizeof(node));
    curr = head;
    runner = curr;
    while (curr != NULL){
        runner = curr;
        while (runner->next != NULL){
            if (curr->data == runner->next->data){
                deleteNode(runner, curr);
            }
            if (runner->next!=NULL)
                runner = runner->next;
        }
        curr = curr->next;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    struct node * list = (node*) malloc(sizeof(node));
    list = createNode(1);
    insertAfter(list,2);
    insertAfter(list, 2);
    insertAfter(list, 3);   
    removedups(list);
    return 0;
}
4

1 回答 1

2

它看起来更像 C 代码，而不是 C++。

如果是面试，尽量使用递归，他们问链表问题主要是看你是否适应。只是为了测试您是否擅长使用不同类型的算法。

你有很多 malloc（这是用于动态内存分配的 C 风格），但是你在哪里释放内存呢？内存泄漏也是他们想听你思考的事情！所以不要犹豫，大声说出来：现在我必须检查我没有弄乱记忆！

于 2013-10-14T18:09:20.510 回答