定义链表结构
struct ListNode{ int val; ListNode *next; ListNode(int v) : val(v), next(NULL) {}}; 非递归反转单链表
ListNode* reverse(ListNode *root){ if (root == NULL || root->next == NULL) return root; ListNode *cur = root->next; root->next = NULL; while (cur != NULL) { ListNode *tmp = cur->next; cur->next = root; root = cur; cur = tmp; } return root;} 递归反转单链表
void reverseRec(ListNode *root, ListNode *&head){ if (root == NULL) return; if (root->next == NULL) { head = root; return; } reverseRec(root->next, head); root->next->next = root; root->next = NULL;} 测试
#includeusing namespace std;struct ListNode{ int val; ListNode *next; ListNode(int v) : val(v), next(NULL) {}};ListNode* createList(ListNode *root){ if (root == NULL) { ListNode *root = new ListNode(0); ListNode *p1 = new ListNode(1); ListNode *p2 = new ListNode(2); root->next = p1; p1->next = p2; return root; }}void tranverse(ListNode *root){ while (root != NULL) { cout << root->val << " "; root = root->next; } cout << endl;}void deleteList(ListNode *root){ while (root != NULL) { delete root; root = NULL; }}ListNode* reverse(ListNode *root){ if (root == NULL || root->next == NULL) return root; ListNode *cur = root->next; root->next = NULL; while (cur != NULL) { ListNode *tmp = cur->next; cur->next = root; root = cur; cur = tmp; } return root;}void reverseRec(ListNode *root, ListNode *&head){ if (root == NULL) return; if (root->next == NULL) { head = root; return; } reverseRec(root->next, head); root->next->next = root; root->next = NULL;} int main(){ ListNode *root = createList(root); //ListNode *root = NULL; tranverse(root); root = reverse(root); tranverse(root); ListNode *head = NULL; reverseRec(root, head); tranverse(head); deleteList(head);}