手撕链表题
第一题，实现链表翻转
第二题，实现链表指定区域翻转
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; struct ListNode* next; ListNode(int x) : val(x), next(nullptr){} }; ListNode* ReverseList(ListNode* head) { //第一题 翻转链表 ListNode* pre = nullptr; ListNode* cur = head; ListNode* nex = nullptr; while (cur) { nex = cur->next; cur->next = pre; pre = cur; cur = nex; } return pre; } ListNode* reverseBetween(ListNode* head, int m, int n) { //第二题 翻转链表指定区间[m,n] ListNode* ans = new ListNode(-1); ans->next = head; ListNode* pre = ans; ListNode* cur = head; ListNode* nex = nullptr; for (int i = 1;i < m;i++) { pre = cur; cur = cur->next; } for (int i = m;i < n;i++) { nex = cur->next; cur->next = nex->next; nex->next = pre->next; pre->next = nex; } return ans->next; } int main() { ListNode* l1 = new ListNode(1); ListNode* l2 = new ListNode(2); ListNode* l3 = new ListNode(3); ListNode* l4 = new ListNode(4); l1->next = l2; l2->next = l3; l3->next = l4; ListNode* ans = reverseBetween(l1,2,4); while (ans) { cout << ans->val << " "; ans = ans->next; } return 0; }
第三题，合并两个有序链表（同样适用于合并k个升序链表）
#include <bits/stdc++.h> using namespace std; struct ListNode { int val; struct ListNode* next; ListNode(int x) : val(x), next(nullptr){} }; ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { // write code here ListNode* ans = new ListNode(-1); ans->next = nullptr; ListNode* cur = ans; while (pHead1 && pHead2) { if (pHead1->val > pHead2->val) { ListNode* x = new ListNode(pHead2->val); pHead2 = pHead2->next; cur->next = x; } else { ListNode* x = new ListNode(pHead1->val); pHead1 = pHead1->next; cur->next = x; } cur = cur->next; } if (pHead1) cur->next = pHead1; if (pHead2) cur->next = pHead2; return ans->next; } int main() { ListNode* l1 = new ListNode(1); ListNode* l2 = new ListNode(2); ListNode* l3 = new ListNode(3); ListNode* l4 = new ListNode(4); ListNode* l5 = new ListNode(5); ListNode* l6 = new ListNode(6); l1->next = l3; l3->next = l5; l2->next = l4; l4->next = l6; ListNode* ans = Merge(l1,l2); while (ans) { cout << ans->val << " "; ans = ans->next; } return 0; }