Reverse Linked List
Reverse a singly linked list.
Example 1:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
分析：
用三个指针 pre,cur,next，紧紧相邻，不断前进，每次将cur.next指向pre。
思路一：迭代
/**
* 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) {
ListNode *pre = NULL;
ListNode *cur = head;
ListNode *next = NULL;
while (cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
思路二：递归
/**
* 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 == NULL || head->next == NULL) {
return head;
}
ListNode* reversedListHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return reversedListHead;
}
};
时间复杂度o(n)，空间复杂度o(n)