408算法题leetcode--第14天

92. 反转链表 II

• 92. 反转链表 II
• 思路：头插法
• 时间：O(n)；空间：O(1)

/*** 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* reverseBetween(ListNode* head, int left, int right) {// 头插法if(head == nullptr) return nullptr;ListNode* dummy_head = new ListNode(-1, head);ListNode* p = dummy_head;for(int i = 0; i < left - 1; i++){p = p->next;}ListNode* cur = p->next;ListNode* next = nullptr;for(int i = 0; i < right - left; i++){next = cur->next;cur->next = next->next;next->next = p->next;p->next = next;}return dummy_head->next;}
};

21. 合并两个有序链表

• 21. 合并两个有序链表
• 时间：O(n+m)；空间：O(1)

/*** 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* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == nullptr) return list2;if(list2 == nullptr) return list1;ListNode* p = list1, *q = list2;ListNode* dummy_head = new ListNode(-1);ListNode* t = dummy_head;while(q && p){if(q->val <= p->val){t->next = q;q = q->next;} else {t->next = p;p = p->next;}t = t->next;}t->next = q == nullptr ? p : q;return dummy_head->next;}
};

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

• 24. 两两交换链表中的节点
• 思路：类似之前的头插法
• 时间：O(n)；空间：O(1)

/*** 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) return head;ListNode* dummy_head = new ListNode(-1, head);ListNode* pre = dummy_head, *cur = dummy_head->next;ListNode* next = nullptr;while(cur && cur->next){next = cur->next;// 头插法cur->next = next->next;next->next = pre->next;pre->next = next;// 向后移动pre = cur;cur = cur->next;}return dummy_head->next;}
};

876. 链表的中间结点

• 876. 链表的中间结点
• 思路：快慢指针
• 时间：O(n)；空间：O(1)

/*** 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* middleNode(ListNode* head) {// 快慢指针：快指针走2步，慢指针走1步ListNode* fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}
};