1. LeetCode24. 两两交换链表中的结点

两两交换链表中的结点

/*解法1：迭代。。设置虚拟头结点*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* res = new ListNode(-1);// 设置一个虚拟头结点res->next = head;// 将虚拟头结点指向head，这样方面后面做删除操作ListNode* cur = res;while(cur->next != nullptr && cur->next->next != nullptr){ListNode* tmp = cur->next;// 记录临时节点ListNode* tmp1 = cur->next->next->next;cur->next = cur->next->next;  // 步骤一cur->next->next = tmp;        // 步骤二cur->next->next->next = tmp1; // 步骤三cur = cur->next->next;// cur移动两位，准备下一轮交换}return res->next;}
};

/*解法2：递归*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {//如果链表结点个数为0或1，这时候直接返回head，不需要交换if(head == nullptr || head->next == nullptr) return head;ListNode* prev = head;ListNode* cur = prev->next;ListNode* next = cur->next;//交换两个节点prev->next = next;cur->next = prev;//以 1->2->3->4->5->nullptr 为例//交换之后为 2->1->3->4->5->nullptr//因为head是指向1的，所有递归调用的结果返回给head->nexthead->next = swapPairs(next);return cur;}
};

解法2图解：

//解法3：
class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* newhead = head->next;ListNode* tmp = nullptr;ListNode* prev = head;ListNode* cur = prev->next;ListNode* next = cur->next;while(prev != nullptr && prev->next != nullptr){cur->next = prev;prev->next = next;if(tmp != nullptr) tmp->next = cur;tmp = prev;prev = next;if(prev != nullptr)cur = prev->next;if(cur != nullptr) next = cur->next;}return newhead;}
};

解法3：是不用虚拟的头结点，直接在原链表交换，是一种不错的思路，但是理解起来不是那么容易，建议上面两种方法的理解，下面是图解过程

2. LeetCode19. 删除链表的倒数第N个节点

删除链表的倒数第N个节点

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {//给链表设置一个虚拟头结点（哨兵结点），有效防止删除正数第一个的情况，避免更新头结点ListNode* res = new ListNode(-1);res->next = head;ListNode* fast = head;ListNode* slow = head;ListNode* prev = res;while(n--)//因为题目中n是有效的，所以我们让快指针先走n步{fast = fast->next;}while(fast)//然后fast和slow一起走{fast = fast->next;prev = slow;//一起走之前，先记录一下slow的位置，当fast走到空时，slow一定走到了倒数第n个节点上slow = slow->next;}prev->next = slow->next;return res->next;}
};

3. LeetCode160.相交链表

相交链表

//解法1：
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* pA = headA;ListNode* pB = headB;//你可以算一算图中的pA走完headA从headB开始走到交点，和pB走完headB从headA开始走到交点距离是一样的while(pA != pB)//pA == pB时退出，表明走到了交点{// pA 将headA链表走完了，就去走headB链表pA = pA == nullptr ? headB : pA->next;// pB 将headB链表走完了，就去走headA链表pB = pB == nullptr ? headA: pB->next;}return pA;}
};//解法2;
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* tailA = headA;ListNode* tailB = headB;int lenA = 1;while(tailA->next)//计算链表A的长度{++lenA;tailA = tailA->next;}int lenB = 1;while(tailB->next)//计算链表B的长度{++lenB;tailB = tailB->next;}if(tailA != tailB)//两个链表都走完了，但是不相等，表明一定没有交点{return nullptr;}int gap = abs(lenB - lenA);//算出长短链表相差多少ListNode* shortlist = headA;ListNode* longlist = headB;if(lenA > lenB)//这里用来准确确定长、短链表{shortlist = headB;longlist = headA;}while(gap--)//让长链表走差距步{longlist = longlist->next;}while(longlist != shortlist)//然后长链表和短链表一起走{longlist = longlist->next;shortlist = shortlist->next;}return longlist;}
};

4. LeetCode141.环形链表

环形链表

思路动图：

双指针法:

快指针先走两步，紧接着慢指针走

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(fast == slow){return true;}}return false;}
};

5. LeetCode142.环形链表II

环形链表II

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow){ListNode* meet = slow;while(meet != head){meet = meet->next;head = head->next;}return head;}}return nullptr;}
};

6. LeetCode138.复制带随机指针的链表

class Solution {
public:Node* copyRandomList(Node* head) {//1.拷贝源节点并链接Node* cur = head;while(cur){Node* copy = new Node(cur->val);copy->next = cur->next;cur->next = copy;cur = copy->next;}cur = head;//2.根据原节点，处理copy节点的randomwhile(cur){Node* copy = cur->next;if(cur->random == nullptr){copy->random = nullptr;}else{copy->random = cur->random->next;}cur = copy->next;}cur = head;//3.把拷贝节点解下来，链接成新链表。同时恢复原链表；Node* copyhead, *copytail;copyhead = copytail = nullptr;while(cur){Node* copy = cur->next;Node* next = copy->next;if(copytail == nullptr){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copy;}cur->next = next;cur = next;}return copyhead;}
};