【C++】“反转链表”相关的题目
1.反转链表：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
（1）这道题是经典的题目了，用迭代的方式解决也是很容易的，代码量也不大。分享一个我个人做题的方式，我会先在题目开头写注释，理清我结题的思路，然后写代码就很容易了。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { //首先需要判断特殊情况 //需要三个指针实现，先记录当前节点的下一个节点，然后把当前节点的后继节点变成前一个节点，然后把当前节点变成前一个节点，然后把下一个节点变成当前节点往后循环，最后要注意链表的头结点边到最后了 //开始撸 if(head == nullptr || head->next == nullptr) return head; ListNode* pPre = nullptr; ListNode* pCur = head; ListNode* pNext = nullptr; while(pCur != nullptr) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; }return pPre; } };
（2）递归解法：简直是优雅
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { //使用递归的方式进行反转，递归反转链表代码太简洁和优雅了，但是要注意基线条件，不能无限循环,使用递归的核心：不要跳到递归里去！ if(head == nullptr || head->next == nullptr) return head; ListNode* last = reverseList(head->next); head->next->next = head; head->next = nullptr; return last; } };
2.反转链表II:
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
（1）递归，空间换时间，我佛了。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { //按照题意，时间复杂度为O(n) //可以使用迭代和递归两种方式进行，时间复杂度都是O(n)，但是递归的空间复杂度为O(n)，而迭代为O(1) //递归解法 if(m == 1) return reverseN(head, n); head->next = reverseBetween(head->next, m-1, n-1); return head; } ListNode* successor = nullptr; ListNode* reverseN(ListNode* head, int n) { if(n==1) { successor = head->next; return head; } ListNode* last = reverseN(head->next, n-1); head->next->next = head; head->next = successor; return last; }
（2）迭代实现
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { //按照题意，时间复杂度为O(n) //可以使用迭代和递归两种方式进行，时间复杂度都是O(n)，但是递归的空间复杂度为O(n)，而迭代为O(1) //迭代解法 ListNode* pCur = head; ListNode* pPre = nullptr; ListNode* pNext = nullptr; ListNode* pPreM = nullptr; ListNode* pM = nullptr; for(int i=0;i<m-1;i++) { pPreM = pCur; pCur = pCur->next; } pM = pCur; for(int j=m;j<=n;j++) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; } if(m != 1) { pPreM->next = pPre; } pM->next = pNext; return m==1? pPre : head; } };
3.K个一组反转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 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: ListNode* reverseKGroup(ListNode* head, int k) { //先反转以head开头的k个元素 //将第k+1个元素作为head递归调用reverseKGroup函数 //将上述两个过程的结果连接起来 //base case 如果最后的元素不足k个，就保持不变 if(head == nullptr) return nullptr; ListNode* a = head; ListNode* b = head; for(int i=0;i<k;i++) { if(b == nullptr) return head; b = b->next; } ListNode* newHead = reverse(a,b); a->next = reverseKGroup(b,k); return newHead; } ListNode* reverse(ListNode* a, ListNode* b) { ListNode* pCur = a; ListNode* pPre = nullptr; ListNode* pNext = nullptr; while(pCur != b) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; } return pPre; } };
