链表刷题笔记（题解出自灵茶山）

2025/2/25 7:26:14 来源：https://blog.csdn.net/lfm147258369/article/details/144381100 浏览: 次关键词：链表刷题笔记（题解出自灵茶山）

反转链表

class Solution
{
public:ListNode* reverseList(ListNode* head){ListNode* cur = head;ListNode* prv = nullptr;while (cur){ ListNode* nxt = cur->next;   cur->next = prv;prv = cur;cur = nxt; }return prv;}
};

在这里插入图片描述

反转倒数第n个链表

难点在于怎么找到要反转的头节点的前面一个结点。
可以使用快慢指针。即两个指针初始化为头节点，都从头节点出发。先让快的指针先走n次，如此就跳过了n个结点。慢指针仍在起点不动
然后，慢指针与快指针再同时往后移动，此时就能发现，慢指针指向的位置就是倒数第n个结点的前一个结点。
这里还没有结束，如果链表只有一个结点。那么我们需要创建一个哨兵结点，在前面，这样就可以解决了

class Solution 
{
public:ListNode* reverseBetween(ListNode* head, int left, int right){ListNode sen(0, head);ListNode* p = &sen;for (int i = 0; i < left - 1; i++){p = p->next;}ListNode* prv = nullptr;ListNode* cur = p->next;for (int i = 0; i < right - left + 1; i++){ ListNode* nxt = cur->next;cur->next = prv;prv = cur;cur = nxt;}p->next->next = cur;p->next = prv;return sen.next;}
};

合并链表

class Solution 
{
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode*tmp1 = list1;ListNode*tmp2 = list2;ListNode*add = new ListNode(0);ListNode*head = add;add->next = nullptr;while (tmp1 != nullptr && tmp2 != nullptr){if (tmp1->val < tmp2->val){add->next = tmp1;tmp1 = tmp1->next;}else{add->next = tmp2;tmp2 = tmp2->next;}add = add->next;}add->next = tmp1 != nullptr ? tmp1 : tmp2;return head->next;}
};

在这里插入图片描述

环形链表

思路仍为快慢指针。但是判断条件要注意。一个乌龟一个兔子，永远不可能相遇，当它们相遇的时候，就说明这是一个环形链表。

class Solution 
{
public:bool hasCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (slow == fast){ return true;}}return false; }
};

回文链表

就是将反转与寻找链表的中间结点结合起来

class Solution
{ListNode* Mid(ListNode* head){ListNode* fast = head;ListNode* slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}ListNode* Reverse(ListNode* head){ListNode* pre = nullptr;ListNode* cur = head;while (cur){ListNode* nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}
public:bool isPalindrome(ListNode* head){ListNode* mid = Mid(head);ListNode* head2 = Reverse(mid);while (head2){if (head->val != head2->val)return false;head = head->next;head2 = head2->next;}return true;}
};