作者:手机用户2502906317 | 来源:互联网 | 2023-10-09 20:09
面试题思路:假设交换A,B,那么交换A和B的next指针,以及AB直接前驱的next指针;特殊情况是AB相邻,做特殊处理即可。structnode{intdata;node*
面试题
思路:
假设交换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;
}