阿里巴巴国际站怎么开店,北京有多少互联网公司,阳江营销网站开发,电视网站免费大全206.反转链表
力扣题目链接(opens new window)
题意#xff1a;反转一个单链表。
示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 1#xff0c;双指针 2#xff0c;递归。递归参考双指针更容易写#xff0c; 为什么不用头插…206.反转链表
力扣题目链接(opens new window)
题意反转一个单链表。
示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 1双指针 2递归。递归参考双指针更容易写 为什么不用头插法呢因为头插法的空间复杂度为ON时间复杂度为On //双指针
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);}};
双指针 递归
