3-链表

链表定义：

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

==20==ERROR: AddressSanitizer: heap-use-after-free on... 出现这种类似错误，是由于链表尾部没有指向null指针。

203. 移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* pre_head = new ListNode(0,head);
        ListNode* cur = pre_head;
        while(cur && cur->next)
        {
            if(cur->next->val == val) cur->next = cur->next->next;
            else cur = cur->next;
        }
        return pre_head->next;
    }
};

707. 设计链表

class MyLinkedList {
public:

    struct LinkNode{
        int val;
        LinkNode *next;
        LinkNode(int va):val(va),next(nullptr){}
    };

    MyLinkedList() {
        phead = new LinkNode(0); //初始化虚拟头节点
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index >( size -1)) return -1;
        else
        {
            LinkNode *temp = phead->next;
            while (index--)
            {
                temp = temp->next;
            }
            return temp->val;
        }
    }

    void addAtHead(int val) { //头插法
        LinkNode *p = new LinkNode(val);
        p->next = phead->next;
        phead->next = p;
        size++;
    }

    void addAtTail(int val) {//尾插法
        LinkNode *p = new LinkNode(val);
        LinkNode *temp = phead;
        while (temp->next!=NULL)
        {
            temp=temp->next;
        }
        temp->next = p;
        size++;
    }

    void addAtIndex(int index, int val) {
        LinkNode *p = new LinkNode(val);
        LinkNode *temp = phead;

        if (index < 0 || index > size ) return;
        else
        {
            while (index--)
            {
                temp = temp->next;
            }
            p->next = temp->next;
            temp->next = p;

            size++;
        }
    }

    void deleteAtIndex(int index) {
        LinkNode *temp = phead;

        if (index >= size || index < 0) {
            return;
        }
        else
        {
            while (index--)
            {
                temp = temp->next;
            }
            temp->next = temp->next->next;

            size--;
        }
    }
private:
    int size;
    LinkNode *phead;
};

206. 反转链表

//1.迭代
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            ListNode* t = cur->next;
            cur->next = pre;
            pre = cur;
            cur = t;
        }
        return pre;
    }
};


//2.递归
class Solution {
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(!cur) return pre;
        ListNode *next = cur->next;
        cur->next = pre;
        return reverse(cur,next);
    }
public:
    ListNode* reverseList(ListNode* head) {
         return reverse(nullptr,head);
    }
};

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

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* prehead = new ListNode(0,head);
        ListNode* cur = prehead;
        while(cur->next && cur->next->next)
        {
            ListNode* t1 = cur->next->next->next;
            ListNode* t2 = cur->next;

            cur->next = cur->next->next;
            cur->next->next = t2;
            t2->next = t1;
            cur = cur->next->next;
        }
        return prehead->next;
    }
};

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

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* pre = new ListNode(0,head);
        ListNode* cur = pre;
        ListNode* p = cur;
        while(n--) cur = cur->next;
        while(cur->next)
        {
            cur = cur->next;
            p = p->next;
        }
        p->next = p->next->next;
        return pre->next;
    }
};

面试题 02.07. 链表相交

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode * A = headA;
        ListNode * B = headB;
        while(A != B)
        {
            A = A ? A->next : headB;
            B = B ? B->next : headA;
        }
        return A;
    }
};

141. 环形链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) return true;
        }
        return false;
    }
};

142. 环形链表 II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        bool is_loop = false;
        while(fast && fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) 
            {
                is_loop = true;
                break;
            }
        }
        if(!is_loop) return NULL;
        slow = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

287. 寻找重复数

和上一题相似，快慢指针，第一次相遇的时候开始，让slow为0，fast为第一次相遇的地点，再次遍历，就能找到环的入口，环的入口就是重复的数。slow = nums[slow] 为移动一下，fast = nums[nums[fast]]为移动两下。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = 0,slow = 0;
        while(true)
        {
            fast = nums[nums[fast]];
            slow = nums[slow];
            if(fast == slow) break;
        }
        int start = 0;
        while(start != fast)
        {
            start = nums[start];
            fast =  nums[fast];
        }
        return start;
    }
};

234. 回文链表

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = NULL;
        //求出链表长度
        int n = 0;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        //翻转前一半的链表
        cur = head;
        int cnt = n / 2;
        while (cnt--)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        if (n % 2 == 1) cur = cur->next;
        while (cur && pre)
        {
            if (cur->val != pre->val) return false;
            cur = cur->next;
            pre = pre->next;
        }
        return true;
    }
};

143. 重排链表

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* cur = head;
        vector<ListNode*> res;
        while(cur)
        {
            res.push_back(cur);
            cur = cur->next;
        }
        int left = 0 , right = res.size() - 1;
        cur = head;
        while(left < right)
        {
            cur->next = res[left++];
            cur = cur->next;
            cur->next = res[right--];
            cur = cur->next;
        }
        if(left == right)
        {
            cur->next = res[left];
            res[left]->next = nullptr;
        }
        else cur->next = nullptr;
    }
};

328. 奇偶链表

==20==ERROR: AddressSanitizer: heap-use-after-free on... 出现这种类似错误，是由于链表尾部没有指向null指针。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* curji_pre = new ListNode(0);
        ListNode* curou_pre = new ListNode(0);
        ListNode* curji = curji_pre;
        ListNode* curou = curou_pre;
        int cnt = 0;
        while (head)
        {
            if (cnt % 2 == 0)
            {
                curou->next = head;
                curou = curou->next;
            }
            else
            {
                curji->next = head;
                curji = curji->next;
            }
            head = head->next;
            cnt++;
        }
        curji->next = nullptr; // 这一句话一定要加
        curou->next = curji_pre->next;
        return curou_pre->next;
    }
};

2. 两数相加

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* prenod1 = new ListNode(0,l1);
        ListNode* prenod2 = new ListNode(0,l2);
        ListNode* res = prenod1;
        int p = 0;
        while(prenod1->next && prenod2->next)
        {
            int sum = (prenod1->next->val + prenod2->next->val + p);
            prenod1->next->val = sum % 10;
            p = sum / 10;
            prenod1 = prenod1->next;
            prenod2 = prenod2->next;
        }
        if(prenod2->next) prenod1->next = prenod2->next;
        while(prenod1->next)
        {
            int sum = (prenod1->next->val  + p);
            prenod1->next->val = sum % 10;
            p = sum / 10;
            prenod1 = prenod1->next;
        }
        if(p) 
        {
            ListNode* t = new ListNode(p,nullptr);
            prenod1->next = t;
        }
        return res->next;
    }
};

148. 排序链表

归并排序

---找到链表中点 --- 使用快慢指针

class Solution {
    ListNode* merege(ListNode* left,ListNode* right)
    {
        if(!left) return right;
        if(!right) return left;
        if(left->val < right->val) 
        {
            left->next = merege(left->next,right);
            return left;
        }
        else
        {
            right->next = merege(right->next,left);
            return right;
        }
    }
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* pre = nullptr;
        while(fast && fast->next)
        {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);

        //两个有序链表的合并
        return merege(left,right);
    }
};

58. 最后一个单词的长度

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;
        if(list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

83. 删除排序链表中的重复元素

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* pre = new ListNode(0,head);
        ListNode* cur = pre;
        while(cur->next && cur->next->next)
        {
            if(cur->next->val == cur->next->next->val)
            {
                cur->next = cur->next->next;
            }
            else cur = cur->next;
        }
        return pre->next;
    }
};

82. 删除排序链表中的重复元素 II

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = new ListNode(0,head);
        ListNode* pre_head = cur;
        while(cur->next && cur->next->next)
        {
            int val = cur->next->val;
            ListNode* tmp = cur->next;
            while(tmp->next && tmp->next->val == val) tmp = tmp->next;
            if(tmp == cur->next) 
            {
                cur->next = tmp;
                cur = cur->next;
            }
            else cur->next = tmp->next;
        }
        return pre_head->next;
    }
};

25. K 个一组翻转链表

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        vector<ListNode*> res;
        ListNode* cur = head;
        while(cur)
        {
            res.push_back(cur);
            cur = cur->next;
        }
        for(int i = 0; i < res.size();i += k)
        {
            if(i + k <= res.size()) reverse(res.begin() + i ,res.begin() + i + k);
            else reverse(res.begin() + i + k, res.end());
        }
        for(int i = 0; i < res.size() - 1; i++)
        {
            res[i]->next = res[i + 1];
        }
        res.back()->next = nullptr;
        return res[0];
    }
};

21. 合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;
        if(list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

138. 复制带随机指针的链表

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return head;
        vector<Node*> res;
        unordered_map<Node*,int> org;
        vector<Node*> news;
        Node* cur = head;
        int cnt = 0;
        while(cur)
        {
            Node* t = new Node(cur->val);
            news.push_back(t);
            org[cur] = cnt++;
            res.push_back(cur);
            cur = cur->next;
        }
        for(int i = 0; i < news.size() - 1; i++)
        {
            news[i]->next = news[i + 1];
            if(res[i]->random) news[i]->random = news[org[res[i]->random]];
        }
        if(res.back()->random != nullptr) news.back()->random = news[org[res.back()->random]];
        return news[0];
    }
};

面试题 02.04. 分割链表

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        vector<ListNode*> less;
        ListNode* pre_head = new ListNode(0,head);
        ListNode* cur = pre_head;
        while(cur->next)
        {
            if(cur->next->val < x)
            {
                less.push_back(cur->next);
                cur->next = cur->next->next;
            }
            else cur = cur->next;
        }
        
        if(less.size() > 0)
        {
            for(int i = 0; i < less.size() - 1; i++) less[i]->next = less[i + 1];
            less.back()->next = pre_head->next;
            return less[0];
        }
        else return pre_head->next;
    }
};

1171. 从链表中删去总和值为零的连续节点

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        if(!head) return head;
        int sum = 0;
        for(ListNode *p = head; p; p = p->next)
        {
            sum += p->val;
            if(sum == 0) return removeZeroSumSublists(p->next);
        }
        head->next = removeZeroSumSublists(head->next);
        return head;
    }
};

237. 删除链表中的节点

class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* pre = node;
        ListNode* r = nullptr;
        ListNode* cur = pre->next;
        while(cur)
        {
            int temp = pre->val;
            pre->val = cur->val;
            cur->val = pre->val;
            if(pre->next && !pre->next->next) r = pre;
            pre = cur;
            cur = cur->next;
        }
        r->next = nullptr;
    }
};