代码随想录算法训练营第4天 | 链表 |

24两两交换列表元素

ListNode* swapPairs(ListNode* head) {
    ListNode* shead = new ListNode();   //初始化
    shead->next = head;
    ListNode* cur = shead;
    ListNode* tmp;

    //确定先后顺序很重要
    while (cur->next!=nullptr && cur->next->next!=nullptr) {
        tmp = cur->next;
        cur->next = cur->next->next;
        tmp->next = cur->next->next;
        cur->next->next = tmp;

        cur = cur->next->next;
    }
    return shead->next;
}

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

难点：实现一次扫描

解法：快慢指针

ListNode* removeNthFromEnd(ListNode* head, int n) {

    ListNode* shead = new ListNode();
    shead->next = head;

    ListNode* fast, *slow;
    fast = shead;
    slow = shead;  //slow指向被删除的前一个元素

    while (n--)
    {
        fast = fast->next;
    }
    
    while (fast->next)
    {
        fast = fast->next;
        slow = slow->next;
    }

    ListNode* tmp = slow->next;
    slow->next = tmp->next;
    delete tmp;
    tmp = nullptr;

    return shead->next;
}

面试题 02.07. 链表相交

长短链表长度差为x，则长链表的前x个元素不可能是相交点，从长链表的第x+1个元素开始比较

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB)
        return 0;
    
    int a = 1, b = 1;
    ListNode* curA, * curB;
    curA = headA;
    curB = headB;

    while (curA->next) {
        a++;
        curA = curA->next;
    }
    while (curB->next) {
        b++;
        curB = curB->next;
    }

    int x = a - b;

    curA = headA;
    curB = headB;

    if (x > 0) {
        while (x--)
            curA = curA->next;
        for (int i = 0; i < b; i++) {
            if (curA == curB)
                return curA;
            else
            {
                curA = curA->next;
                curB = curB->next;
            }
        }
    }
    else {
        x = -x;
        while (x--)
            curB = curB->next;
        for (int i = 0; i < a; i++) {
            if (curA == curB)
                return curB;
            else
            {
                curA = curA->next;
                curB = curB->next;
            }
        }
    }
    return nullptr;
}

142环形链表II

• 若链表有环，快慢指针可能会相遇
• 快指针+=2，慢指针+=1，快指针以每步1步长的速度接近慢指针，不会错过，在慢指针进入环的第一圈一定会被快指针追上
  
• (x + y) * 2 = x + y + n (y + z)
  x = (n-1)(y+z) + z
  • 当n=1时，x = z
  • 当n>1时，快指针多走了n-1圈
  • index1从相遇点出发，index2从head出发，将在环的入口相遇

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};