[LeetCode] Reverse Linked List(递归与非递归反转链表)

Reverse a singly linked list.

解题思路

对于非递归实现，思路是依次将从第二个结点到最后一个结点的后继设为头结点，然后将该节点设为头结点（需记住将原头结点的后继设为空）。 对于递归实现，首先反转从第二个结点到最后一个结点的链表，然后再将头结点放到已反转链表的最后，函数返回新链表的头结点。

非递归实现代码1//Runtime:10 msclass Solution {public:ListNode* reverseList(ListNode* head) {;ListNode *pre = head;ListNode *cur = head->next;while (cur != NULL){pre->next = cur->next;cur->next = head;head = cur;cur = pre->next;}return head;}};非递归实现代码2//Runtime:22 msclass Solution{public:ListNode* reverseList(ListNode* head){;ListNode *cur = head->next;head->next = NULL;while (cur != NULL){ListNode *temp = cur->next;cur->next = head;head = cur;cur = temp;}return head;}};递归实现代码//Runtime:10 msclass Solution{public:ListNode* reverseList(ListNode* head){head->next == NULL) return head;ListNode *newhead = reverseList(head->next);head->next->next = head;head->next = NULL;return newhead;}};

测试代码如下：

void printList(ListNode *head){while(head != NULL){cout<<head->val<<” “;head = head->next;}cout<<endl;}void dropList(ListNode *head){if (head == NULL) return;ListNode *temp;while (head != NULL){temp = head->next;delete head;head = temp;}}int main(){ListNode *head = new ListNode(0);ListNode *cur = head;for (int i = 0; i < 10; i++){ListNode *newnode = new ListNode(floor(rand()%100));cur->next = newnode;cur = newnode;}printList(head);Solution s;head = s.reverseList(head);printList(head);dropList(head);}

，不如意的时候不要尽往悲伤里钻，想想有笑声的日子吧