力扣206反转链表

206.反转链表

力扣题目链接(opens new window)

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

1，双指针

2，递归。递归参考双指针更容易写，

为什么不用头插法呢，因为头插法的空间复杂度为O（N），时间复杂度为O（n）

 //双指针
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode * cur = head;//指向当前操作结点ListNode * pre = NULL;//指向cur的前一个结点ListNode * temp;if(cur== NULL|| cur ->next ==NULL){return head;}while(cur!=NULL){temp  = cur->next;//temp记录cur的下一个结点cur->next = pre;//cur指向前一个结点pre = cur;//pre后移cur = temp;//cur后移}return pre;//最后返回pre作为头节点}
};

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/递归
class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur) {if(cur == NULL)return pre;//递归终止入口ListNode * temp = cur->next;cur->next = pre;return reverse(cur,temp);}ListNode* reverseList(ListNode*head){return reverse(NULL,head);}};

双指针：                                                                                        递归：