| class Vector { |
| public: |
| Vector(int n) : size(n), count(0) { |
| data = new int[size]; |
| } |
| |
| ~Vector() { |
| delete[] data; |
| } |
| |
| bool expand() { |
| std::cout << "expand v from " << size << " to " << 2 * size << std::endl; |
| int *p = new int[2 * size]; |
| if (p == nullptr) return false; |
| for (int i = 0; i < count; ++i) { |
| p[i] = data[i]; |
| } |
| delete[] data; |
| data = p; |
| size *= 2; |
| return true; |
| } |
| |
| bool insert(int pos, int val) { |
| if (pos < 0 || pos > count) return false; |
| if (size == count && !expand()) return false; |
| for (int i = count - 1; i >= pos; i--) { |
| data[i + 1] = data[i]; |
| } |
| data[pos] = val; |
| ++count; |
| return true; |
| } |
| |
| bool erase(int pos) { |
| if (pos < 0 || pos >= count) return false; |
| for (int i = pos + 1; i < count; ++i) { |
| data[i - 1] = data[i]; |
| } |
| --count; |
| return true; |
| } |
| |
| void output() const { |
| int len = 0; |
| for (int i = 0; i < size; ++i) { |
| len += std::printf("%3d", i); |
| } |
| std::cout << std::endl; |
| for (int i = 0; i < len; ++i) std::cout << "-"; |
| std::cout << std::endl; |
| for (int i = 0; i < count; ++i) { |
| std::printf("%3d", data[i]); |
| } |
| std::cout << std::endl << std::endl; |
| } |
| |
| private: |
| int size, count; |
| int *data; |
| }; |
| #define DL 3 |
| #define STR(n) #n |
| #define DIGIT_LEN_STR(n) "%" STR(n) "d" |
| |
| class Node { |
| public: |
| int data; |
| Node *next; |
| Node(int val) : data(val), next(nullptr) {} |
| }; |
| |
| class LinkedList { |
| public: |
| LinkedList() : head(nullptr) {} |
| ~LinkedList() { |
| clear(); |
| } |
| |
| void insert(int pos, int val) { |
| Node dummy(0); |
| dummy.next = head; |
| Node *p = &dummy; |
| Node *node = new Node(val); |
| for (int i = 0; i < pos; i++) { |
| if (p->next == nullptr) break; |
| p = p->next; |
| } |
| node->next = p->next; |
| p->next = node; |
| head = dummy.next; |
| } |
| |
| void clear() { |
| Node *p = head; |
| while (p != nullptr) { |
| Node *q = p->next; |
| delete p; |
| p = q; |
| } |
| head = nullptr; |
| } |
| |
| void output(int flag = 0) const { |
| int n = 0; |
| for (Node *p = head; p; p = p->next) n += 1; |
| for (int i = 0; i < n; i++) { |
| printf(DIGIT_LEN_STR(DL), i); |
| printf(" "); |
| } |
| printf("\n"); |
| for (Node *p = head; p; p = p->next) { |
| printf(DIGIT_LEN_STR(DL), p->data); |
| printf("->"); |
| } |
| printf("\n"); |
| if (flag == 0) printf("\n\n"); |
| } |
| |
| bool find(int val) const { |
| Node *p = head; |
| int n = 0; |
| while (p) { |
| if (p->data == val) { |
| output(1); |
| int len = n * (DL + 2) + 2; |
| for (int i = 0; i < len; i++) printf(" "); |
| printf("^\n"); |
| for (int i = 0; i < len; i++) printf(" "); |
| printf("|\n"); |
| return true; |
| } |
| n += 1; |
| p = p->next; |
| } |
| return false; |
| } |
| private: |
| Node *head; |
| }; |
法一:迭代
| class Solution { |
| public: |
| ListNode* reverseList(ListNode* head) { |
| ListNode*temp; |
| ListNode*cur=head; |
| ListNode *pre=nullptr; |
| while(cur){ |
| temp=cur->next; |
| cur->next=pre; |
| pre=cur; |
| cur=temp; |
| } |
| return pre; |
| } |
| }; |
法二:递归
| class Solution { |
| public: |
| ListNode* reverseList(ListNode* head) { |
| if (head == nullptr || head->next == nullptr) { |
| return head; |
| } |
| ListNode*tail=head->next; |
| ListNode*newhead=reverseList(head->next); |
| tail->next=head; |
| head->next=nullptr; |
| return newhead; |
| } |
| }; |
快慢指针:
| class Solution { |
| public: |
| bool hasCycle(ListNode *head) { |
| if(head==nullptr||head->next==nullptr)return false; |
| ListNode*slow=head; |
| ListNode*fast=head->next; |
| while (slow != fast) { |
| if (fast == nullptr || fast->next == nullptr) { |
| return false; |
| } |
| slow = slow->next; |
| fast = fast->next->next; |
| } |
| return true; |
| } |
| }; |
| class Solution { |
| public: |
| int getnext(int x){ |
| int d,y=0; |
| while(x){ |
| d=x%10; |
| y+=d*d; |
| x/=10; |
| } |
| return y; |
| } |
| bool isHappy(int n) { |
| int p=n,q=n; |
| while(q!=1){ |
| p=getnext(p); |
| q=getnext((getnext(q))); |
| if(p==q&&p!=1)return false; |
| } |
| return true; |
| } |
| }; |
| class Solution { |
| public: |
| int getlength(ListNode* head) { |
| int n = 0; |
| while (head) { |
| head = head->next; |
| n += 1; |
| } |
| return n; |
| } |
| ListNode* rotateRight(ListNode* head, int k) { |
| if (head == NULL) return head; |
| int n = getlength(head); |
| k %= n; |
| if (k == 0) return head; |
| ListNode *p = head, *q = head; |
| k++; |
| while(k--) p = p->next; |
| while (p) p = p->next, q = q->next; |
| p = q->next; |
| q->next = NULL; |
| q = p; |
| while (q->next != NULL) q = q->next; |
| q->next = head; |
| return p; |
| } |
| }; |
| class Solution { |
| public: |
| ListNode* removeNthFromEnd(ListNode* head, int n) { |
| ListNode*newhead=new ListNode(0); |
| newhead->next=head; |
| ListNode*p=newhead; |
| ListNode*q=head; |
| while(n--)q=q->next; |
| while(q){ |
| p=p->next; |
| q=q->next; |
| } |
| p->next=p->next->next; |
| return newhead->next; |
| } |
| }; |
| class Solution { |
| public: |
| ListNode *detectCycle(ListNode *head) { |
| ListNode*fast=head; |
| ListNode*slow=head; |
| while(fast!=NULL&&fast->next!=NULL){ |
| slow=slow->next; |
| fast=fast->next->next; |
| if(slow==fast){ |
| ListNode*p1=head; |
| ListNode*p2=slow; |
| while(p1!=p2){ |
| p1=p1->next; |
| p2=p2->next; |
| } |
| return p1; |
| } |
| } |
| return nullptr; |
| } |
| }; |
递归:
| class Solution { |
| public: |
| ListNode* reverseBetween(ListNode* head, int left, int right) { |
| if(left==1&&right==1)return head; |
| if(left!=1){ |
| head->next=reverseBetween(head->next,left-1,right-1); |
| } |
| else{ |
| ListNode*tail=head->next; |
| ListNode*newhead=reverseBetween(head->next,left,right-1); |
| head->next=tail->next; |
| tail->next=head; |
| head=newhead; |
| } |
| return head; |
| } |
| }; |
