2. 链表

LeetCode.203.移除链表元素

// 虚拟节点直接遍历
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummy = new ListNode(0,head);
        ListNode *now = dummy;
        while(now){
            if(now->next && now->next->val == val){
                now->next = now->next->next;
            }else{
                // 上面的删除了下一节点后，相当于自动移动了
                // 所以仅在不匹配的情况下移动
                now = now->next;
            }
        }
        return dummy->next;
    }
};

LeetCode.206.反转链表

// 让当前节点只向"已反转链表pre"
// 再更新"已反转链表pre"
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* now = head;
        while(now){
            ListNode *tmp = now;
            now = now->next;
            tmp -> next = pre;
            pre = tmp;
        }
        return pre;
    }
};

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

// 快慢指针
// 快的先走N步
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* first = head;
        ListNode* second = new ListNode(0,head);
        ListNode* dummy = second;
        for(int i = 1;i <= n;i++){
            first = first->next;
        }
        while(first){
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return dummy->next;
    }
};

LeetCode.142.环形链表II

// 找到第一个相遇的节点
// 然后从起点和相遇点出发，再次相遇即为入环点
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* first = new ListNode(0, head);
        ListNode* second = new ListNode(0, head);
        while(first){
            if(first->next == nullptr || first->next->next == nullptr) return nullptr;
            first = first->next->next;
            second = second->next;
            if(first == second) break;
        }
        second = new ListNode(0,head);
        while(second != first){
            second = second->next;
            first = first->next;
        }
        return second;
    }
};