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

LeetCode题目

注意事项

• 如果说循环的边界不好判断的话，可以尝试先写循环内的逻辑，再考虑循环的条件
• 一定要考虑好特殊情况（如本题：单元素数组，空数组等）

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* tmp1 = dummyhead;

        if (tmp1->next == NULL)
            return dummyhead->next;
        while (tmp1->next->next != NULL) {
            ListNode* tmp = tmp1->next->next;
            tmp1->next->next = tmp->next;
            tmp->next = tmp1->next;
            tmp1->next = tmp;
            tmp1 = tmp1->next->next;
            if (tmp1->next == NULL)
                break;
        }
        return dummyhead->next;
    }
};

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

LeetCode题目

注意事项

• 什么时候可以使用双指针？固定距离

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* pointer1 = dummyhead,* pointer2 = dummyhead;
        for (int i = 0; i < n; i++)
            pointer2 = pointer2->next;
        while(pointer2->next != NULL) {
            pointer2 = pointer2->next;
            pointer1 = pointer1->next;
        }
        pointer1->next = pointer1->next->next;
        return dummyhead->next;
    }
};

面试题02.07.链表相交

LeetCode题目

注意事项

• 本题有一个灵巧的解法，原理如下：
  设A的长度为a，B的长度为b，共有长度为c，则A，B从头开始同时走，走到结尾就换到对方的头结点，相遇时走的路程都是a+b-c

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode *pointerA = headA, *pointerB = headB;
        int nulla = 0, nullb = 0;
        if (pointerA == NULL || pointerB == NULL)
            return NULL;
        while (nulla < 2 && nullb < 2) {
            if (pointerA == pointerB)
                return pointerA;
            if (pointerA->next == NULL) {
                nulla++;
                pointerA = headB;
            } else
                pointerA = pointerA->next;
            if (pointerB->next == NULL) {
                nullb++;
                pointerB = headA;
            } else
                pointerB = pointerB->next;
        }
        return NULL;
    }
};

142.环形链表II

LeetCode题目

注意事项

• 环形列表的通用想法：快慢指针
• 考虑好各种特殊情况（各种NULL）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* A = head, * B = head;
        if (A == NULL) return NULL;
        if (A->next == NULL) return NULL;
        if (A->next->next == NULL) return NULL;

        A = A->next;
        B = B->next->next;

        while (A != B) {
            if (A == NULL || B == NULL || B->next == NULL)
                return NULL;
            else {
                A = A->next;
                B = B->next->next;
            }
        }
        A = head;
        while (A != B) {
            A = A->next;
            B = B->next;
        }
        return A;
    }
};