Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
迭代版
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if(!head || !head->next) return head; ListNode* tail = head; ListNode* cur = tail->next; ListNode* next = cur; tail->next = NULL; while(next != NULL){ next = cur->next; cur ->next = tail; tail = cur; cur = next; } return tail; } };递归版:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseListInit(ListNode* head, ListNode* newhead){ if(head == NULL) return newhead; ListNode*next = head->next; head->next = newhead; return reverseListInit(next, head); } ListNode* reverseList(ListNode* head) { return reverseListInit(head, NULL); } };