首页 > 代码库 > 单链表逆转

单链表逆转

// p 为指向非空单链表中第一个结点的指针,本算法逆转链表并返回逆转后的头指针。基本思路是:如果链表中只有一 个结点,则空操作,否则先逆转a2开始的链表,然后将 a1联接到逆转后的链表的表尾(即a2)之后。 

 1 //递归方法逆转 单链表 2 Node* RecReverseList(Node* head) 3 { 4     if(!head || !head->next) 5     { 6         return head; 7     } 8  9     Node *newhead = RecReverseList(head->next);10     head->next->next = head;11     head->next = NULL;12     return newhead;13 }14 15 //非递归方式逆转 单链表16 Node* RecReverseList(Node* head)17 {18     if(!head || !head->next)19     {20         return head;21     }22     Node* p1 = head;23     Node* p2  = p1->next;24     head->next = NULL;25 26     while(p2)27     {28         p1 = p2;29         p2 = p2->next;30         p1->next = head;31         head = p2;32     }33     return head;34 }