//逆转单链表 struct node *reverse_LList(node *head) { //以p作为当前结点处理,头结点为逆转前的头结点 struct node *p,*q,*temp; if(head == NULL) cout << "空表" << endl;//头结点为0,空表 q = head; //q指向头结点 p = head->next; //p指向头结点后一个结点 head = p; //头结点进一位 temp = p->next; //保存当前结点指针域 q->next = NULL; //逆转头结点为尾结点的情况,头指针为空 p->next = q; //后一个结点指向头结点 while(temp->next != NULL) //判断当前结点的后一结点指针域是否为空,即判断是否为尾结点 { q = head; //q指向头结点 p = temp; //p指向头结点后一个结点 temp = p->next; //保存当前结点指针域 head = p; //头结点进一位 p->next = q; //后一个结点指向头结点 } //此时temp表示以前的尾结点,p表示temp结点的前一结点 head = temp; //逆转尾结点为头结点 head->next = p; //头结点指针域指向p return head; } //逆转循环链表 struct node *reverse_LList(node *head) { //以p作为当前结点处理, struct node *p,*q,*temp,*s; int count = 0; if(head == NULL) cout << "空表" << endl;//头结点为0,空表 do { q = head; //q指向头结点 temp = p->next; //保存当前结点指针域 p = temp; //p指向头结点后一个结点 head = p; //头结点进一位 p->next = q; //后一个结点指向前一结点 if(count == 0) {q->next = s} //记录下第一个结点 count++; }while(temp->next != head); //判断当前结点的后一结点指针域是否为逆转前的头结点,即判断是否为尾结点 //循环完之后,此时temp表示以前的尾结点,p表示temp结点的前一结点 head = temp; //逆转尾结点为头结点 head->next = p; //头结点指针域指向p s = head; //s指向头结点 return head; } //逆转双向链表 struct node *reverse_bilateral_LList(node *head) { struct node *p,*q,*tp,*tq; //处理尾结点的情况, 即将head结点逆转为尾结点. q = head; //q指向头结点 p = head->next; //p指向头结点后一结点 tp = p->next; //tp存储p的右指针域 //先处理p结点 p->next = q; //p的右指针指向q p->prior = tp; //p的左指针指向它的下一个元素 //再处理q结点 q->prior = p; //q结点左指针指向p q->next = NULL; //q结点右指针为空,表示逆转后尾结点next为空 while(tp->next != NULL) { tp = p->next; //tp存储p的右指针域 p = tp; //p结点进一位 tq = q->next; //tq存储q的右指针域 q = tq; //q结点进一位 //先处理p结点 p->next = q; p->prior = tp; //再处理q结点 q->prior = p; q->next = head; //q结点右指针区域指向该结点的前一个元素,即head结点. head = q; //head结点进一位 } //最后再处理头结点情况,即将尾结点逆转为头结点. head = tp; head->next = p; head->prior = NULL; return head; } 深受liupengty前辈教诲,不敢不举一反三,以谢厚望,如有错误还请前辈指教
