头文件与结构体

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_map>
#include <iso646.h>
#include <queue>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

创建链表

ListNode * CreateList(){
    ListNode * tail = new ListNode(0);
    ListNode * head = tail;
    for(int i = 0;i < 5;i++){
        ListNode * p = new ListNode(i);
        tail -> next = p;
        tail = p;
    }

    return head->next;
}

展示链表

void ShowList(ListNode * head){
    while(head){
        cout << head ->val <<" ";
        head = head->next;
    }

    cout << endl;
}

翻转链表

ListNode* ReverseList(ListNode * head){
    ListNode * cur = head;
    ListNode * pre = nullptr;
    ListNode * temp = nullptr;
    while(cur){
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

复杂链表的复制

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

Node* copyRandomList(Node* head){
    Node * tail = new Node(-1);
    Node * temp = head;
    unordered_map<Node* ,Node*> hash;
    while(temp){
        hash[temp] = new Node(temp->val);
        temp = temp->next;
    }
    temp = head;
    while(temp){
        hash[temp] ->next = hash[temp->next];
        hash[temp] ->random = hash[temp->random];
        temp = temp->next;
    }

    return hash[head];
}

剑指offer 18 删除链表的节点

ListNode * DeleteNode(ListNode * head,int val){
    if(head->val == val) return head->next;
    ListNode *temp = head;
    while(temp->next){
        if(temp->next->val == val){
            temp->next = temp->next->next;
            break;
        }
        temp = temp->next;
        if(temp == nullptr) break;
    }
    return head;
}

剑指 Offer 06. 从尾到头打印链表

vector<int> reversePrint(ListNode* head) {
    vector<int> v;
    ListNode * temp = head;
    while(temp){
        v.push_back(temp->val);
        temp = temp->next;
    }

    reverse(v.begin(), v.end());
    return v;
}

剑指 Offer 25. 合并两个排序的链表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode * node = new ListNode(-1);
    ListNode * temp = node;
    ListNode * temp1 = l1;
    ListNode * temp2 = l2;
    while(temp1 && temp2){
        if(temp1->val <= temp2->val ){
            node->next = temp1;
            temp1 = temp1->next;
        }else{
            node->next = temp2;
            temp2 = temp2->next;
        }

        node = node -> next;
    }

    node -> next = temp1 == nullptr ? temp2:temp1;


    return temp->next;
}

剑指 Offer 22. 链表中倒数第k个节点

ListNode* getKthFromEnd(ListNode* head, int k) {
    ListNode *temp = head;
    int cnt = 0;
    while(temp){
        cnt++;
        temp = temp->next;
    }

    cnt = cnt - k;
    temp = head;
    while(cnt--){
        temp = temp->next;
    }

    return temp;

}

剑指 Offer 52. 两个链表的第一个公共节点

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode * tempA = headA;
    ListNode * tempB = headB;
    while(tempA != tempB){
        tempA = tempA!= nullptr ? tempA->next:headB;
        tempB = tempB!= nullptr ? tempB->next:headA;
    }
    return tempA;
}

141. 环形链表

bool hasCycle(ListNode *head) {
    ListNode * fast = head;
    ListNode * slow = head;
    while(fast != nullptr && fast->next != nullptr){
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) return true;
    }
    return false;
}

161. 旋转链表

ListNode* rotateRight(ListNode* head, int k) {
    if(head == nullptr) return nullptr;
    int cnt = 0;
    ListNode * temp = head;
    while(temp){
        cnt++;
        temp = temp->next;
    }
    k = k % cnt;
    if(k == 0) return head;
    k = cnt - k - 1;
    temp = head;
    while(k--){
        temp = temp->next;
    }
    ListNode * temp2 = temp;
    ListNode * res = temp->next;
    while(temp2->next){
        temp2 = temp2->next;
    }

    temp2->next = head;
    temp->next = nullptr;
    return res;
}

725. 分隔链表

vector<ListNode*> splitListToParts(ListNode* root, int k) {
    vector<ListNode *> res;
    ListNode *temp = root;
    int cnt = 0;
    while (temp) {
        cnt++;
        temp = temp->next;
    }

    if (cnt / k == 0) {
        temp = root;
        while (temp) {
            ListNode *temp2 = temp;
            res.push_back(temp);
            temp = temp->next;
            temp2->next = nullptr;
        }
        k = k - cnt;
        while (k--) {
            res.push_back(nullptr);
        }
    } else {
        vector<int> nums;
        int extra = cnt % k;
        int num = cnt / k;
        for (int i = 0; i < k; i++) {
            if (extra > 0)
                nums.push_back(num + 1);
            else
                nums.push_back(num);
            extra--;
        }
        ListNode *temp2 = root;
        for (int i = 0; i < k; i++) {
            temp = temp2;
            ListNode *temp3 = temp;
            for (int j = 1; j <= nums[i]; j++) {
                temp2 = temp->next;
                if (j == nums[i]) temp->next = nullptr;
                if (j < nums[i])
                    temp = temp->next;
            }
            res.push_back(temp3);
        }


    }

    return res;
}

环形链表II

ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while(fast != nullptr){
        slow = slow -> next;
        if(fast ->next == nullptr) return nullptr;
        fast = fast ->next->next;
        if(fast == slow){
            ListNode *ptr = head;
            while(ptr != slow){
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    
    return nullptr;
}

奇偶分链表

ListNode* oddEvenList(ListNode* head) {
    if(head == nullptr) return nullptr;
    ListNode * evenhead = head->next;
    ListNode * odd = head;
    ListNode * even = evenhead;
    while(even && even->next){
        odd ->next = even->next;
        odd = odd->next;
        even ->next = odd->next;
        even= even->next;
    }

    odd->next= evenhead;
    return head;
}

区间翻转链表

ListNode * reverseList(int times,ListNode * head){
    ListNode * temp = nullptr;
    ListNode * cur = head;
    ListNode * pre = nullptr;
    while(times--){
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    head-> next = temp;

    return pre;
}

ListNode * reverseList2(ListNode * head){
    ListNode * temp = nullptr;
    ListNode * cur = head;
    ListNode * pre = nullptr;
    while(cur){
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    //head-> next = temp;

    return pre;
}


ListNode* reverseBetween(ListNode* head, int left, int right) {
    int times = left - 1;
    ListNode * headtemp = head;
    ListNode * temp = nullptr;
    int length = 0;
    while(head){
        head = head->next;
        length++;
    }
    if(length == right && left == 1){
        return reverseList2(headtemp);
    }

    head = headtemp;
    while(times--){
        temp = head;
        head = head->next;
    }

    if(temp == nullptr){
        return reverseList(right - left + 1,head);
    }

    temp->next =  reverseList(right - left + 1,head);

    return headtemp;

}

合并K个链表

ListNode* mergeTwoLists(ListNode *heada,ListNode *headb){
    if(!heada || !headb) return heada ? heada:headb;
    ListNode * node = new ListNode(-1);
    ListNode * head = node;
    while(heada&&headb){
        if(heada->val < headb->val){
            node->next = heada;
            heada = heada->next;
        }else{
            node->next = headb;
            headb = headb->next;
        }

        node = node->next;
    }


    node->next =  heada ? heada:headb;
    return head->next;


}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode *ans = nullptr;
    for(int i = 0;i < lists.size();i++){
        ans = mergeTwoLists(ans, lists[i]);
    }
    return ans;
}
最后修改:2021 年 05 月 02 日 11 : 21 PM
如果觉得我的文章对你有用,请随意赞赏