面试题 02.07. 链表相交

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pa = headA;
        ListNode *pb = headB;
        while (pa != pb) {
            pa = (pa == nullptr? headB:pa->next);
            pb = (pb == nullptr? headA:pb->next);
        }
        return pa;
    }
};

技巧

设置两个指针，都遍历完两个链表即可。

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dumy = new ListNode();
        dumy->next = head;
        ListNode *fast = dumy;
        while(n--) {
            fast = fast->next;
        }
        ListNode *slow = dumy;
        fast = fast->next;
        while(fast!=nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        
        ListNode *temp = slow->next;
        slow->next = slow->next->next;
        delete temp;
        return dumy->next;
    }
};

技巧

1.设置虚拟头节点；方便处理空链表或者只有一个元素的情况。反正这种链表题目都可以考虑设置虚拟头节点
2.注意fast 要多走一步。这样slow就可以走到第N-1个节点，方便删除操作
3.注意记得delete回收内存空间

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

https://leetcode.cn/problems/swap-nodes-in-pairs/

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dumy = new ListNode(0);
        dumy->next = head;
        ListNode *cur = dumy;
        while(cur->next !=nullptr && cur->next->next) {

            ListNode *temp = cur->next;
            ListNode *temp1 = cur->next->next->next;

            cur->next = temp->next;
            cur->next->next = temp;
            cur->next->next->next = temp1;

            cur = temp;
        }
        ListNode *result = dumy->next;
        ListNode *temp = dumy;
        delete dumy;
        return result;
    }
};

技巧

1.还是要增加虚拟节点。
2.注意把图画好就可以。循环终止条件是cur != nullptr & cur->next != nullptr，其实就是当前节点下一个、下下一个节点不为空，这两个节点才做交换操作。初始条件就是ListNode *cur = dumy;

142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) {
            return nullptr;
        }

        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != nullptr && fast->next  != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow && fast !=nullptr) {
                ListNode *index1 = head;
                ListNode *index2 = fast;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }


        return nullptr;
    }
};

技巧

1. 快慢指针。同类型题目判断链表是否有环
2. 把图和公式画清楚就ok