巧妙的构造虚拟头结点。可以使遍历处理逻辑更加统一;
灵活使用递归。构造递归条件,使用递归可以巧妙的解题。不过需要注意有些题目不能使用递归,因为递归深度太深会导致超时和栈溢出。
leetcode第92题:https://leetcode-cn.com/problems/reverse-linked-list-ii/
//本次步骤如下:
//(1)先设置一个虚拟头节点,避免判断边界条件
//(2)设置三个指针,一个指向left,一个指向left前面的节点(a), 一个指向left后面的节点(b)
//(3)指向left的节点,和指向left后面的节点一起循环移动,移动的过程中,调换指针指向方向,具体看代码
//(4)循环终止条件就是left的节点到达right,
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(-1), *h = dummy;
dummy->next = head;
for (int i = 0; i < left - 1; i ++, h = h->next);
ListNode* a = h->next, *b = a->next;//设置那三个指针
right -= left;//循环条件
while (right > 0){
right --;
ListNode* tmp = b->next;
b->next = a;//调换方向
a = b;
b = tmp;//a, b指针继续向后挪一个位置
}
h->next->next = b;//h本来是指向a的,现在a是最后一个right节点,因此这个节点要执行原来right之后的一个节点
h->next = a; //指向逆序后的right节点;
return dummy->next;
}
这一类题目最容易想到的解法一应该就是双指针了
//寻找中间节点应该是最简单的了,只要设置两个指针fast和slow指针,fast指针每次走两个位置,slow指针每次走一个位置
//当fast指针走到最后的时候,也就是中间节点;
ListNode* middleNode(ListNode* head) {
ListNode *quick = head, *slow = head;
//1 2 3 4 5 6
while (quick->next){
quick = quick->next;
if (quick->next){
quick = quick->next;
}
slow = slow->next;
}
return slow;
}
这应该是一种特解了,下面来看看通解’
//像这种删除倒数第几个节点,在倒数第几个节点前面插入节点,输出倒数第几个节点的值都可以用下面的解法
//(1)先设置虚拟头节点
//(2)设置一个移动节点first指向原本的头节点,让其移动n个位置,,这个时候,然后first和虚拟头节点一起向后移动,
//(3)当first=nullptr,第二个指针指向的位置就是倒数第n个节点前面的节点;之后就可以进行删除,插入,查询操作了
ListNode* removeNthFromEnd(ListNode* head, int n) {
//0 1 2 3 4 5
ListNode* dummy = new ListNode(0, head);
ListNode* first = head;
ListNode* second = dummy;
for (int i = 0; i < n; i++){
first = first->next;
}
while (first){
first = first->next;
second = second->next;
}
second->next = second->next->next;
return dummy->next;
}
//合并两个链表是合并多个n个链表的基础,这里合并只新创建一个虚拟头节点,其他的在原先的两个链表上操作;
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* l3 = new ListNode();
ListNode* head = l3;
while (l1 && l2){
if (l1->val >= l2->val){
l3->next = l2;
l3 = l2;
l2 = l2->next;
}else{
l3->next = l1;
l3 = l1;
l1 = l1->next;
}
}
if (l1){
l3->next = l1;
}
if (l2){
l3->next = l2;
}
return head->next;
}
//这种合并k个链表的,要用到合并思想,把k个拆成两两合并
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* l3 = new ListNode();
ListNode* head = l3;
while (l1 && l2){
if (l1->val >= l2->val){
l3->next = l2;
l3 = l2;
l2 = l2->next;
}else{
l3->next = l1;
l3 = l1;
l1 = l1->next;
}
}
if (l1){
l3->next = l1;
}
if (l2){
l3->next = l2;
}
return head->next;
}
ListNode* merge(vector <ListNode*> &lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = l + ((r - l) >> 1);
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists1(vector<ListNode*>& lists){
return merge(lists, 0, lists.size() - 1);
}
//链表归类,最容易想到的方法应该是分割之后再合并
ListNode* partition(ListNode* head, int x) {
//先分割再拼接
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* bigInX = new ListNode(), *p = bigInX;
ListNode* smallInX = new ListNode(), *q = smallInX;
while (head){
if (head->val >= x){
bigInX->next = head;
bigInX = head;
}else{
smallInX->next = head;
smallInX = head;
}
head = head->next;
}
smallInX->next = p->next;
bigInX->next = nullptr;
return q->next;
}
//也可以再原有的空间上操作,,设置一个尾节点,符合条件就移动到尾节点后,然后把该节点设置成尾节点
ListNode* partition1(ListNode* head, int x) {
ListNode* dummy = new ListNode(), *h = dummy;
if (head == nullptr)return nullptr;
dummy->next = head;
ListNode* p = head;
while (p->next){
p = p->next;
}
ListNode* tail = p, *q = tail;
p = head;
while (p != q->next){
if(p->val >= x){
tail->next = p;
h->next = p->next;
p = p->next;
tail = tail->next;
}else{
p = p->next;
h = h->next;
}
}
tail->next = nullptr;
return dummy->next;
}
//跟上面题目是一样的
ListNode* oddEvenList(ListNode* head) {
ListNode* odd = new ListNode();
ListNode* even = new ListNode();
ListNode* oddTail = odd;
ListNode* evenTail = even;
int i = 1;
while (head){
if (i & 1){
oddTail->next = head;
oddTail = head;
}else{
evenTail->next = head;
evenTail = head;
}
head = head->next;
i ++;
}
oddTail->next = even->next;
evenTail->next = nullptr;
return odd->next;
}
这一类题目只要分为两类,判断是否有环,判断哪个是进环的第一个节点;
(1)判断是否有环,只要设置两个指针,然后让一个指针每次走两个,一个每次走一个,,如果之后两个指针能相遇,则说明有环;
(2)而找出哪个是进环的第一个节点这样是远远不够的,,比如:假设非环部分长度为a,环部分长度为b,如果两者相遇,那必然是快指针走的位置为慢指针的两倍,,如果a = b 那第一次相遇就是入环第一个节点,那是特殊情况,所以我们要在第一次相遇后,,让快指针从头节点重新再走一次,慢指针仍然继续走,,这是为了人快指针比慢指针夺走这个a,这样相遇必然是在入环第一个节点
//判断是否有环
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head, *slow = head;
while (true){
if (fast == nullptr || fast->next == nullptr)return false;
fast = fast->next;
if (fast != nullptr)
fast = fast->next;
slow = slow->next;
if (slow == fast)return true;
}
return false;
}
//找出入环的第一个节点
ListNode* detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (true){
if (fast == nullptr || fast->next == nullptr)return nullptr;
fast = fast->next;
if (fast){
fast = fast->next;
}
slow = slow->next;
if (fast == slow)break;
}
fast = head;
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
这个就比较单纯了,只能用归并排序
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head, ListNode* tail) {
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortList(head, mid), sortList(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
} else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。