【代码随想录算法训练营——Day4】链表——24.两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题02.07.链表相交、142.环形链表II

LeetCode题目链接
https://leetcode.cn/problems/swap-nodes-in-pairs/
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
https://leetcode.cn/problems/linked-list-cycle-ii/

题解
24.两两交换链表中的节点
可以模拟一下画个图，注意设立虚拟头结点。

19.删除链表的倒数第N个节点
注意要找到被删除结点的前一个结点（这道题也是被提示这个思路才做出来的）。

面试题02.07.链表相交
启发思路：先求出两个链表长度，再求长度的差值，让长链表的指针移动到与短链表剩余长度相同的位置。
注意此题只能在leetcode上跑出正确结果，本地IDE运行时两个链表是单独建成不相交，所以无结果，下面附着的代码是本地代码。

142.环形链表II
拿到题目第一反应，开一个10的4次方的数组，作为判定链表中结点值是否出现过的判定（假定题目给的链表结点没有重复的，有重复的就不行了），如果当前结点的next结点的值显示为判定过，则链表存在环。
看了题解，采用快慢指针法。
本题根据题解，有两个地方需要注意，一是快慢指针遍历时的循环条件，我在代码里注释掉的是我自己写的，此时当结点只有一个时就会报错，因为快指针不存在下一个结点的next，下一个结点已然是NULL，因此在循环遍历时是判断快指针的存在与否与快指针的下一个结点存在与否；二是根据题解用数学方法求出环入口的位置，这段代码的循环要放在第一个循环里面，因为只有在第一个循环中发现有环后才能再寻找环入口。代码很简洁，重要的是思想。

代码

//24.两两交换链表中的节点
#include <iostream>
#include <vector>
using namespace std;


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 == NULL) return NULL;
        ListNode* pre1 = new ListNode;
        pre1->next = head;
        ListNode* pre2 = head;
        ListNode* pre3 = pre1;
        while (pre1!= NULL && pre2!= NULL && pre1->next != NULL && pre2->next != NULL) {
            int tmp = pre2->next->val;
            pre2->next->val = pre1->next->val;
			pre1->next->val = tmp;
            pre1 = pre1->next->next;
            pre2 = pre2->next->next;
        }
        return pre3->next;
    }
};

ListNode* createList(vector<int> nums) {
    if (nums.size() == 0) return NULL;
    ListNode* cur = new ListNode(nums[0]);
    cur->next = NULL;
    ListNode* pre = cur;
    int len = 1;
    while (len < nums.size()) {
		cur->next = new ListNode(nums[len]);
        cur = cur->next;
        len++;
    }
    return pre;
}

int main() {
    Solution s;
    vector<int> nums = { 1, 2, 3, 4, 5 };
	ListNode* node = createList(nums);
    ListNode* tmp = node;
    while (tmp != NULL) {
        printf("%d ", tmp->val);
        tmp = tmp->next;
    }
    printf("\n");
	node = s.swapPairs(node);
    while (node != NULL) {
        printf("%d ", node->val);
        node = node->next;
    }
    return 0;
}

//19.删除链表的倒数第N个节点
#include <iostream>
#include <vector>
using namespace std;

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) {}
};


ListNode* createList(vector<int>nums) {
    ListNode* cur = new ListNode(nums[0]);
    ListNode* pre = cur;
    int len = 1;
    while (len < nums.size()) {
        cur->next = new ListNode(nums[len]);
        cur = cur->next;
        len++;
    }
    return pre;
}

class Solution {
public:
    int getListLen(ListNode* head) {
        int len = 0;
        while (head) {
			len++;
			head = head->next;
        }
        return len;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len = getListLen(head);
        int num = len - n;
        ListNode* pre = new ListNode;
        pre->next = head;
        ListNode* pre2 = pre;
        while (num--) {
            pre = pre->next;
        }
        pre->next = pre->next->next;
        return pre2->next;
    }
};

int main() {
	vector<int> nums = { 1,2 };
    ListNode* node = createList(nums);
    ListNode* tmp = node;
    while (tmp) {
        printf("%d ", tmp->val);
        tmp = tmp->next;
    }
    printf("\n");
    Solution s;
    node = s.removeNthFromEnd(node, 1);
    while (node) {
        printf("%d ", node->val);
        node = node->next;
    }
    return 0;
}

//面试题02.07.链表相交
#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* createList(vector<int> nums) {
    if (nums.size() == 0) return NULL;
    ListNode* cur = new ListNode(nums[0]);
    ListNode* pre = cur;
    int len = 1;
    while (len < nums.size()) {
		cur->next = new ListNode(nums[len]);
        cur = cur->next;
        len++;
    }
    return pre;
}


class Solution {
public:
    int getListLen(ListNode* head) {
        int len = 0;
        while (head) {
            len++;
            head = head->next;
        }
        return len;
    }

    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lenA = getListLen(headA), lenB = getListLen(headB);
        if (lenA < lenB) {
            ListNode* tmp = headA;
            headA = headB;
            headB = tmp;
        }
		int diff = abs(lenA - lenB);
        while (diff) {
            headA = headA->next;
            diff--;
        }
		while (headA && headB) {
			if (headA == headB) return headA;
			headA = headA->next;
			headB = headB->next;
		}
        return NULL;
    }
};


int main() {
    vector<int> nums1 = { 4,1,8,4,5 }, nums2 = { 5,0,1,8,4,5 };
	ListNode* headA = createList(nums1);
    ListNode* headB = createList(nums2);
	Solution s;
	ListNode* node = s.getIntersectionNode(headA, headB);
    ListNode* tmp = headA;
    while (tmp) {
        printf("%d ", tmp->val);
        tmp = tmp->next;
    }
    printf("\n");
    tmp = headB;
    while (tmp) {
        printf("%d ", tmp->val);
        tmp = tmp->next;
    }
    printf("\n");
    while (node) {
		printf("%d ", node->val);
		node = node->next;
    }
    return 0;
}

//142.环形链表II
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
		ListNode* slow = head, *fast = head;
        //do {
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            //} while (slow != fast && slow && fast);
            if (slow == fast) {
                ListNode* index1 = head, * index2 = slow;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};