今天去昆仑在线笔试，其中一题是写一个单链表逆置函数，节点如下：

struct Node

{

    int Value;

    Node *next;

};

之前还真没有写过，只好想了个笨办法了。结构体比较简单，那只交换value的值好了。

Node *getByNum(int n,Node* head)

{

    int i=0;

    while(n--)

    {

        if(head->next != NULL)

            head = head->next;

        else

            return NULL;

    }

    return head;

}

Node *reverse(Node *head)

{

    Node *tmp = head,*n1,*n2;

    int count = 0;

    while(tmp != NULL)

    {

        count++;

        tmp = tmp->next;

    }

    int temp = 0;

    for (int i=0;i<count/2;i++)

    {

        n1 = getByNum(i,head);

        n2 = getByNum(count-i-1,head);

        temp = n1->Value;

        n1->Value = n2->Value;

        n2->Value = temp;

    }

    return head;

}

回来之后拿笔在纸上画了画，发现根本不用这么麻烦。。定义一组（3个）节点指针，循环遍历一次就可以逆置过来。

Node *reverse2(Node *head)

{

    Node *F,*S,*T;

    F = head;

    S = F->next;

    T = S->next;

    head->next = NULL;

    while(T!=NULL)

    {

        S->next = F;

        F = S;

        S = T;

        T = T->next;

    }

    S->next = F;

    return S;

}

看来自己的基本功不扎实啊，以后得多练练基础了。

 本文用 发布