代码随想录二刷Day2

203. 移除链表元素 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        //移除链表元素的核心就是找到需要删除元素的前一个节点
        //为了所有链表删除操作统一，可以采用虚拟头节点，dummyNode
        ListNode* dummyNode = new ListNode(0);
        dummyNode -> next = head;
        ListNode* cur = dummyNode;
        while(cur != nullptr && cur -> next != nullptr)
        {   
            //删除一个节点之后不能直接向后移动，要停在原位防止漏删
            if(cur->next->val == val)
            {
                cur->next = cur->next->next;
            }
            else
            {
                cur = cur->next;
            }
        }
        return dummyNode->next;
    }
};

707. 设计链表 - 力扣（LeetCode）

class MyLinkedList {
public:
    struct LinkedNode
    {
        int val;
        LinkedNode* next;
        LinkedNode(int val): val(val), next(nullptr){}
    };
 
    MyLinkedList() {
        dummyHead = new LinkedNode(0);
        size = 0;
    }
    
    int get(int index) {
        //无效下标
        if(index < 0 || index >= size)
            return -1;
        //有效下标
        LinkedNode* cur = dummyHead;
        //需要得到index指向的节点
        for(int i = 0; i <= index; i++)
        {
            cur = cur->next;
        }
        return cur->val;
 
    }
    
    void addAtHead(int val) {
        LinkedNode* cur = dummyHead;
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
 
    }
    
    void addAtTail(int val) {
        LinkedNode* cur = dummyHead;
        while(cur->next != nullptr)
        {
            cur = cur->next;
        }
        LinkedNode* newNode = new LinkedNode(val);
        cur->next= newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index < 0 || index > size)
            return;
        LinkedNode* cur = dummyHead;
        LinkedNode* newNode = new LinkedNode(val);
        for(int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
 
    }
    
    void deleteAtIndex(int index) 
    {
        if(index < 0 || index >= size)
            return;
        LinkedNode* cur = dummyHead;
        for(int i = 0; i < index; i++)
        {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        size--;
 
    }
private:
    int size;
    LinkedNode* dummyHead;
};
 
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206. 反转链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        //反转链表主要是在反转的同时不能丢失后面的节点，统一操作可以使用一个指向nullptr的pre指针
        
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            ListNode* nNode = cur->next;
            cur -> next = pre;
            pre = cur;
            cur = nNode;
        }
 
        return pre;
 
    };
};

24. 两两交换链表中的节点 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
      if(!head || head->next == nullptr)
        return head;
      
      ListNode* dummyHead = new ListNode(0);
      dummyHead->next = head;
      ListNode* cur = head;
      ListNode* pre = dummyHead;
      while(cur != nullptr && cur->next != nullptr)
      {
         ListNode* next = cur->next;
         cur->next = next->next;
         next->next = pre->next;
         pre->next = next;
 
         pre = cur;
         cur = cur->next;
      }
      return dummyHead->next;
    }
};

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       ListNode* dummyHead = new ListNode(0);
       dummyHead->next = head;
       
       //使用双指针用于定位到倒数第N个结点之前一个的节点
       ListNode* slow = dummyHead;
       ListNode* fast = dummyHead;
 
       //fast指针从dummyHead虚拟节点开始向前先走n+1步
       while(n-- && fast != nullptr)
       {
          fast = fast->next;
       }
       fast = fast->next;
       //然后快慢指针一起向前，到fast走到null后，slow所在节点的下一个节点就是要求被删除的节点
       while(fast)
       {
        slow = slow->next;
        fast = fast->next;
       }
       slow->next = slow->next->next;
       return dummyHead->next;
       
 
    }
};

面试题 02.07. 链表相交 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pointerA = headA;
        ListNode* pointerB = headB;
        while(pointerA != pointerB)
        {
            pointerA = pointerA != nullptr? pointerA->next: headB;
            pointerB = pointerB != nullptr? pointerB->next: headA;
        }
        return pointerA;
    }
};

142. 环形链表 II - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            {
                ListNode* index1 = head;
                ListNode* index2 = slow;
                while(index1 != index2)
                {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2;
            }
        }
        return NULL;
    }
};