day04 - 链表part02

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

思路：设置dummy头结点，然后循环，条件是，如果cur->next 和cur->next->next都不是空，就进行交换。

交换就是用两个临时节点保存，先cur指向第二个，第二个再指向第一个，第一个再指向第三个。

代码

ListNode* swapPairs(ListNode* head) {
    ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
    dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
    ListNode* cur = dummyHead;
    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;
    }
    return dummyHead->next;
}

力扣19. 删除倒数第n个节点

思路：快慢指针，快指针先走n步，然后快慢指针一起走，快指针到末尾时，慢指针就是倒数第n个节点

要设置虚拟头结点，因为删除的时候要拿到前一个结点，设置虚拟头结点可以统一删除的操作，包括第一个节点

代码

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(0, head);
    ListNode* slow = dummyHead;
    ListNode* fast = dummyHead;
    //快指针先走n步
    while (n-- && fast != nullptr)
    {
        fast = fast->next;
    }
    //如果快指针的下一个不为空，也就是快指针走到最后一个了，此时慢指针刚好是倒数第n+1个节点
    while (fast->next != nullptr)
    {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return dummyHead->next;
​
}

力扣面试题 02.07. 链表相交

思路：计算出各自链表长度，长度之差就是快指针先前进的长度，如果有相交的话就两个指针会相遇

代码

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* curA = headA;
    int sizeA = 0;
    int sizeB = 0;
    while (curA != NULL)
    {
        sizeA++;
        curA = curA->next;
    }
    ListNode* curB = headB;
    while (curB != NULL)
    {
        sizeB++;
        curB = curB->next;
    }
    curA = headA;
    curB = headB;
    if (sizeB > sizeA)
    {
        swap(sizeA, sizeB);
        swap(curA, curB);
    }
    int n = sizeA - sizeB;
    for (int i = 0; i < n; i++)
    {
        curA = curA->next;
    }
    while(curA && curB)
    {
        if (curA == curB)
        {
            return curA;
        }
        curA = curA->next;
        curB = curB->next;
    }
    return NULL;
}