代码随想录算法训练营第四天 | 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点,02.07. 链表相交,142.环形链表II

day4

24. 两两交换链表中的节点

/**
 * Definition for singly-linked list.
 * 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 == nullptr || head->next == nullptr) return head;
        ListNode *result = new ListNode();
        ListNode *p = head;  // 前一节点
        ListNode *q = head->next; // 后一节点
        ListNode *temp = result;
        result->next = head;
        while (q != nullptr) {
            p->next = q->next;
            q->next = p;
            temp->next = q;
            temp = p;
            if (temp->next == nullptr || temp->next->next == nullptr) break;
            p = temp->next;
            q = p->next;
        }
        head = result->next;
        delete result;
        return head;
    }
};

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

/**
 * Definition for singly-linked list.
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode *result = new ListNode();
        result->next = head;
        ListNode *p = result;
        ListNode *q = head;
        while(n--) {
            q = q->next;
        }
        while (q != nullptr) {
            q = q->next;
            p = p->next;
        }
        q = p->next;
        p->next = q->next;
        delete q;
        q = result->next;
        delete result;
        return q;
    }
};

面试题 02.07. 链表相交

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int length(ListNode* L) {
        ListNode *p = L;
        int num = 0;
        while(p != NULL) {
            num++;
            p = p->next;
        } 
        return num;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = length(headA);
        int lenB = length(headB);
        int subLen = 0;
        ListNode *p = headA;
        ListNode *q = headB;
        if (lenA > lenB) {
            subLen = lenA - lenB;
            while(subLen--) p = p->next;
        } else {
            subLen = lenB - lenA;
            while(subLen--) q = q->next;
        }
        while (q != NULL && p != NULL) {
            if (q == p) return q;
            q = q->next;
            p = p->next;
        }
        return NULL;
    }
};

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) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) {  // 相遇有环
                slow = head;
                while(slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return fast;
            }
        }
        return NULL;
    }