随想录Day 4 ||24.两两交换、19.删除倒数第n个、 02.07. 链表相交、142. 环形链表 II、链表总结

*********

19.删除链表倒数第n个节点

面试题 02.07. 链表相交

142. 环形链表 II

*********

思路

1，搞上虚拟头结点，方便操作

2，三个指针

3，注意结束判断

（下面是我看了思路后写出来的）

（看了一眼卡尔哥的，差不多，不改了）

typedef struct ListNode ListNode;
struct ListNode* removeNthFromEnd(struct ListNode* obj, int n) {
    if (obj == NULL)
        return NULL;
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = -1;
    head->next = obj;

    ListNode *a = head, *b = head;
    int i = 0;
    while (i < n) {
        if (b->next == NULL)
            return obj;
        b = b->next;
        i++;
    }
    while (b->next != NULL) {
        b = b->next;
        a = a->next;
    }
    ListNode* temp;
    temp = a->next;
    a->next = a->next->next;
    free(temp);
    return head->next;
}

面试题 02.07. 链表相交

思路：尾对齐法

两两分别首尾相接，如果有交点肯定会重合 alt

typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA,
                                     struct ListNode* headB) {
    if (headA == NULL || headB == NULL)
        return NULL;
    ListNode *a = headA, *b = headB;
    int cnt = 0;
    while (a != NULL && b != NULL) {
        if (a == b)
            return a;
        a = a->next;
        b = b->next;
        if (a == NULL && cnt < 2) {
            a = headB;
            cnt++;
        }
        if (b == NULL && cnt < 2) {
            b = headA;
            cnt++;
        }
    }
    return NULL;
}

142. 环形链表 II

思路：快慢指针（追击相遇（bushi））

1、让fast每次走两步，slow每次走一步，这样两指针每次相对移动一次，如果有环肯定会相遇

2、根据画图得出相遇后，起点到交点与相遇点到交点的关系

（第二遍写了还是不会） alt （自己手搓版）

typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    ListNode* fast = head;
    ListNode* slow = head;
    do {
        if (fast->next == NULL || fast->next->next == NULL)
            return NULL;
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != slow);
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

（学习后版）

typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast->next != NULL && fast->next->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;
}