【leetcode】链表反转题目总结

206. 反转链表

全部反转

递归法和迭代法

/*** 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 || head->next == nullptr) {return head;}// 1. 递归法// ListNode* last = reverseList(head->next);// head->next->next = head;// head->next = nullptr;// return last;// 2. 迭代法ListNode* pre = nullptr;ListNode* cur = head;while (cur != nullptr) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}head->next = nullptr;return pre;}
};

25. K 个一组翻转链表

分组反转

/*** 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:// 反转区间[a,b)的元素，左闭右开ListNode* reverseAb(ListNode* a, ListNode* b) {ListNode* pre = nullptr;ListNode* cur = a;while (cur != b) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}ListNode* reverseKGroup(ListNode* head, int k) {// base caseif (head == nullptr) {return nullptr;}ListNode* a = head;ListNode* b = head;for (int i = 0; i < k; ++i) {// 不足 k 个，不需要反转，base caseif (b == nullptr) {return head;}b = b->next;}// 反转前 k 个元素ListNode* newHead = reverseAb(a, b);// 递归反转后续链表并连接起来a->next = reverseKGroup(b, k);return newHead;}
};

24. 两两交换链表中的节点

其实就是两个一组反转链表，利用上个题目的方式：

/*** 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:// 反转区间[a,b)的元素，左闭右开ListNode* reverseAb(ListNode* a, ListNode* b) {ListNode* pre = nullptr;ListNode* cur = a;while (cur != b) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}ListNode* reverseKGroup(ListNode* head, int k) {// base caseif (head == nullptr) {return nullptr;}ListNode* a = head;ListNode* b = head;for (int i = 0; i < k; ++i) {// 不足 k 个，不需要反转，base caseif (b == nullptr) {return head;}b = b->next;}// 反转前 k 个元素ListNode* newHead = reverseAb(a, b);// 递归反转后续链表并连接起来a->next = reverseKGroup(b, k);return newHead;}ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}return reverseKGroup(head, 2);}
};

递归法

/*** 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* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}ListNode* newHead = head->next;ListNode* nextPairs = newHead->next;newHead->next = head;head->next = swapPairs(nextPairs);return newHead;}
};

迭代法

/*** 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* swapPairs(ListNode* head) {ListNode* dummy = new ListNode(-1, head);ListNode* node = dummy;while (node->next != nullptr && node->next->next != nullptr) {ListNode* node1 = node->next;ListNode* node2 = node->next->next;node->next = node2;node1->next = node2->next;node2->next = node1;node = node1;}return dummy->next;}
};

92. 反转链表 II

/*** 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:// 反转区间[a,b)的元素，左闭右开ListNode* reverseAb(ListNode* a, ListNode* b) {ListNode* pre = nullptr;ListNode* cur = a;while (cur != b) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummy = new ListNode(-1);dummy->next = head;// 寻找到反转区间ListNode* a = dummy;ListNode* b = dummy;for (int i = 0; i < right; i++) {if (i < left - 1) {a = a->next;}b = b->next;}ListNode* tailHead = b->next;// 反转区间ListNode* newHead = reverseAb(a->next, tailHead);// 区间前后链接a->next->next = tailHead;a->next = newHead;return dummy->next;}
};

234. 回文链表

/*** 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* head) {ListNode* pre = nullptr;ListNode* cur = head;while (cur != nullptr) {ListNode* next = cur->next;cur->next = pre;pre = cur;cur = next; }return pre;}bool isPalindrome(ListNode* head) {if (head == nullptr) return true;ListNode* fast = head;ListNode* slow = head;while (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;}if (fast != nullptr) {slow = slow->next;}ListNode* p1 = head;ListNode* p2 = reverse(slow);while (p2 != nullptr) {if (p1->val != p2->val) return false;p1 = p1->next;p2 = p2->next;}return true;}
};