• Total Accepted: 191329
• Total Submissions: 435675
• Difficulty: Easy
• Contributors: Admin

Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

来源： 

分析

---

递归版本：

reverseList返回反续后的新头节点

1 2 3 4 5 6 7 8 9 10 11

class  Solution { public :      ListNode* reverseList(ListNode* head) {          if (head == NULL || head->next == NULL)  return  head;                    ListNode* nhead = reverseList(head->next);          head->next->next = head;          head->next = NULL;          return  nhead;      } };

非递归版本

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class  Solution { public :      ListNode* reverseList(ListNode* head) {          ListNode* dummy = NULL;          ListNode* pre = dummy;          ListNode* cur = head;          ListNode* next;          while (cur != NULL){              next = cur->next;              cur->next = pre;              pre = cur;              cur = next;          }          return  pre;      } };