单链表交换任意两个元素（不包括表头）

面试题

思路：

假设交换A，B，那么交换A和B的next指针，以及AB直接前驱的next指针；

特殊情况是AB相邻，做特殊处理即可。

struct node

{

    int data;

    node* next;

};

// find the previous node of p in the singly linked list head

node* FindPre(node*head, node*p)

{

    node*q = head;

    while(q)

    {

        if(q->next == p)

        {

            return q;

        }

        else

        {

            q = q->next;

        }

    }

    return NULL;

}

// swap the two nodes p & q in the singly linked list head

// Pre-condition: p, q are not head of the list

node* swap(node*head, node*p, node*q)

{

    if ( head == NULL || p == NULL || q == NULL )

    {

        cout<<"invalid parameter: NULL"<

        return head;

    }

    // P->Q

    if (p->next == q)

    {

        node* pre_p = FindPre(head, p);

        pre_p->next = q;

        p->next = q->next;

        q->next = p;

    }

    else if (q->next == p)// Q->P

    {

        node* pre_q = FindPre(head, q);

        pre_q->next = p;

        q->next = p->next;

        p->next = q;

    }

    else if ( p != q)

    {

        node* pre_p = FindPre(head, p);

        node* pre_q = FindPre(head, q);

        node* after_p = p->next;

        // node* after_q = q->next;

        p->next = q->next;  // p->after_q

        q->next = after_p;  // q->after_p

        pre_p->next = q;    // pre_p->q

        pre_q->next = p;    // pre_q->p

    }

    return head;

}