目录
一、反转链表 类型
二、双指针类型
三、链表合并类型
四、链表排序
一、反转链表 类型
206. 反转链表
/*** 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) {auto cur = head;ListNode *pre = NULL;while(cur){auto next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}
};//递归实现
class Solution {
public:ListNode* reverseList(ListNode* head) {if(!head || !head->next )return head;ListNode* node = reverseList(head->next);head->next->next = head;head->next = nullptr;return node;}
};
92. 反转链表 II
/*** 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) {int cnt = n-m+1;ListNode *fake = new ListNode(-1);fake->next = head;auto p = head;auto prem = fake;--m;while(m--){prem = p;p = p->next;}auto cur = p;ListNode *pre = nullptr;while(cnt--){auto nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}prem ->next = pre;p->next = cur;return fake->next;}
};
24. 两两交换链表中的节点
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode *i = nullptr, *ii = nullptr,*iii = nullptr;if(head == nullptr || head->next == nullptr)return head;iii = new ListNode(0);iii->next = head;head = iii;i = head;ii = i->next;iii = ii->next;while(iii){ii->next = iii->next;iii->next = ii;i->next = iii;i = ii;ii = i->next;if(!ii)break;else {iii = ii->next;}}return head->next;}
};//递归实现class Solution {
public:ListNode* swapPairs(ListNode* head) {if(!head) return nullptr;if(!head->next) return head;auto i = head->next;head->next = swapPairs(i->next);i->next = head;return i; }
};
25. K 个一组翻转链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode *pre = nullptr,*cur = head,*next = nullptr,*check = head;int cnt = 0;while(cnt < k && check)check = check->next,cnt++;//条件满足if(cnt == k){cnt = 0;while(cnt < k && cur){next = cur->next;cur->next = pre;pre = cur;cur = next;cnt++;}if(cur){head->next = reverseKGroup(next,k);}return pre;}else return head; }
};/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode *L = head;ListNode *res = new ListNode(0);ListNode *pre = res;res->next = head;while(L){int n = k;ListNode *inside = L;// 检查是否可以翻转while(n && inside){inside = inside->next;n--;}if(n == 0){//说明符合k哪么反转就OK了n = k;ListNode *p1 = inside;ListNode *p2 = L;ListNode *p3 = p2;while(n){p3 = p2->next;p2->next = p1;p1 = p2;p2 = p3;n --;}pre->next = p1; pre = L;}L = inside;}return res->next;}
};
二、双指针类型
160. 相交链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {auto pa = headA, pb = headB;if(!pa || !pb)return nullptr;while(pa != pb){pa = pa? pa->next:headB;//两个指针必定会在相交处相遇,因为a+b+c = b+c+apb = pb? pb->next:headA;}return pa;}
};
141. 环形链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(!head || !head->next)return false;auto fast = head->next->next,slow = head->next;while(fast != slow){if(!fast || !slow) return false;slow = slow->next;if(!fast->next)return false;fast = fast->next->next;}return true;}
};
142. 环形链表 II
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head || !head->next)return NULL;auto slow = head->next,fast = head->next->next;while(slow != fast){if(!slow || !fast || !fast->next)return NULL;fast = fast->next->next;slow = slow->next;}fast = head;while(slow!=fast){slow = slow->next;fast = fast->next;}return fast;}
};
三、链表合并类型
21. 合并两个有序链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode *head = new ListNode(0);ListNode *cur = head;while(l1 && l2){if(l1->val < l2->val){cur->next = l1;cur = cur->next;l1 = l1->next;}else {cur->next = l2;cur = cur->next;l2 = l2->next;}}cur->next = l1? l1:l2;return head->next;}
};
23. 合并K个排序链表
struct cmp{bool operator () (const ListNode* x,const ListNode* y)const{return x->val > y->val;}
};
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {auto cmp = []( ListNode* x, ListNode* y)->bool { return x->val > y->val;};priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> pq(cmp);for(int i = 0;i<lists.size();i++){if(lists[i])pq.push(lists[i]);}ListNode *head = nullptr,*cur = nullptr,*tmp = nullptr;while(!pq.empty()){tmp = pq.top();pq.pop();if(!cur)head = tmp;else cur->next = tmp;cur = tmp; if(tmp->next)pq.push(tmp->next);}return head;} };
四、链表排序
147. 对链表进行插入排序
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* insertionSortList(ListNode* head) {ListNode* dummy = new ListNode(INT_MIN);auto cur = head;auto pre = dummy;while(cur){pre = dummy;auto nxt = cur->next;while(pre->next && pre->next->val < cur->val)pre = pre->next;cur->next = pre->next;pre->next = cur;cur = nxt;}return dummy->next;}
};
148. 排序链表
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:void Swap(ListNode *l1,ListNode *l2){int tmp = l1->val;l1->val = l2->val;l2->val = tmp;}void quick_sort(ListNode* head,ListNode* tail){if(head == tail)return;int pivot = head->val;auto p1 = head;auto p2 = p1->next;while(p2 && p2 != tail){if(p2->val < pivot){p1 = p1->next;Swap(p1,p2);}p2 = p2->next;}Swap(head,p1);quick_sort(head,p1);quick_sort(p1->next,tail);}ListNode* sortList(ListNode* head) {quick_sort(head,nullptr);return head;}
};/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if(!head || !head->next)return head;auto fast = head;auto slow = head;auto pre = head;while(fast && fast->next){fast = fast->next->next;pre = slow;slow = slow->next;}pre->next = nullptr;auto l1 = sortList(head);auto l2 = sortList(slow);return merge(l1,l2);}ListNode* merge(ListNode* l1,ListNode* l2){if(!l1)return l2;if(!l2)return l1;if(l1->val <= l2->val){l1->next = merge(l1->next,l2);return l1;}else {l2->next = merge(l1,l2->next);return l2;}}
};