反转链表
自己写的版本
处理分四种类型
- 链表为空
- 链表长度为1
- 链表长度为2
- 链表大于等于三
#include <iostream> #include <vector> #include<algorithm> using namespace std; 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* reverseList(ListNode* head) { ListNode *cur ; ListNode* temp1, * temp2 ; if(head == nullptr || head->next == nullptr) return head;//处理链表为空或者长度为1 if(head->next->next == nullptr)//处理链表长度为2 { temp1 = head; temp2 = head->next; temp2->next = temp1; temp1->next = nullptr; return temp2; } //处理链表长度为3及其以上 temp1 = head; cur = temp1->next; temp2 = cur->next; while (temp2 != nullptr) { cur->next = temp1; if (temp1 == head) { temp1->next = nullptr; temp1 = cur; } else temp1 = cur; cur = temp2; if(cur->next != nullptr) temp2 = cur->next;//检查链表是否到底 else { cur->next = temp1; break; } } return cur; } }; int main() { vector<int> head = { 1,2,3,4,5,6 }; ListNode* head_test = new ListNode(0); ListNode* test , *cur = head_test; Solution a; for (int i = 0; i < head.size(); i++) { ListNode* temp = new ListNode(head[i]); cur->next = temp; cur = cur->next; } cur->next = nullptr; cur = head_test; cout << "cur list" << endl; while (cur->next != nullptr) { cout << cur->val << ' '; cur = cur->next; } cout << cur->val << endl; test = a.reverseList(head_test->next); while (test->next != nullptr) { cout << test->val << ' '; test = test->next; } cout << test->val << ' '; return 0; }
双指针法
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *cur ; ListNode* temp1, * temp2 ; cur = head; temp1 = nullptr; while (cur) { temp2 = cur->next; cur->next = temp1; temp1 = cur; cur = temp2; } return temp1; } };
递归法
class Solution { public: ListNode* reverse(ListNode *pre , ListNode * cur) { if (cur == nullptr)return pre; ListNode* temp = cur->next; cur->next = pre; return reverse(cur , temp); } ListNode* reverseList(ListNode* head) { return reverse(nullptr , head); } };
二刷
/** * 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* reverseList(ListNode* head) { if(head == nullptr) return head; ListNode *pre = nullptr; ListNode *cur = head; ListNode *cur_next = cur->next; while(cur != nullptr) { cur_next = cur->next; cur->next = pre; pre = cur; cur = cur_next; } return pre; } };
