代码随想录1刷—链表篇

链表理论基础

• 链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数	//建议写 不写也没问题
};
1
2
3
4
5
6

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);
1

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;
1
2

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

删除及添加图示

注意：C++里最好是再手动释放这个D节点，释放这块内存。

性能分析

203.移除链表元素

虚拟头结点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;	//1
                cur->next = cur->next->next;
                delete tmp;					//2   1和2是删除该结点，防止其占用内存
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

双指针

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != NULL && head->val == val) {
            head = head->next;
        }
        
        ListNode* cur = head;  //  当前节点
        ListNode* pre = head;  //  保存删除节点的前一节点
        while (cur != NULL) {
            if (cur->val == val) {
                pre->next = cur->next;
            } else {
                pre = cur;
            }
            cur = cur->next;
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

递归

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr) {
            return nullptr;
        }
        //删除原链表中头节点后面值为 val 的元素的节点，直接将 removeElements(head->next, val) 的结果存放到 head->next 中，再判断 head->val 是否等于 val。
        head->next = removeElements(head->next,val);
        return head->val==val ? head->next : head;
    }
};
1
2
3
4
5
6
7
8
9
10
11

707.设计链表

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    LinkedNode* dummyhead;
    int size;

    MyLinkedList() {
        dummyhead = new LinkedNode(0);  //虚拟头结点
        size = 0;
    }
    
    int get(int index) {
        if(index > (size-1) || index < 0) return -1;
        LinkedNode* cur = dummyhead->next;
        for(int i = index; i > 0; i--){
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = dummyhead->next;
        dummyhead->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyhead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) return;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyhead;
        for(int i = index; i > 0; i--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index > (size-1) || index < 0)  return;
        LinkedNode* cur = dummyhead;
        for(int i = index; i > 0; i--) {
            cur = cur ->next;
        }
            LinkedNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
            size--;
    }
};

/**
 * 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

206.反转链表

双指针

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode*temp;
        ListNode*cur = head;
        ListNode*pre = nullptr;
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

递归

class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode*cur) {
        if(cur == nullptr)  return pre;
        ListNode*temp = cur->next;
        cur->next = pre;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr,head);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

24.两两交换节点

虚拟头结点

class Solution {
public:
    ListNode* swapPairs(ListNode* head){
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head;                // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* one = cur->next; 
            ListNode* two = cur->next->next;
            ListNode* three = cur->next->next->next; 

            cur->next = two;        // 步骤一
            two->next = one;        // 步骤二
            one->next = three;      // 步骤三

            cur = cur->next->next;           // cur移动两位，准备下一轮交换
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归

class Solution {
public:
    ListNode* swapPairs(ListNode* head){
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* one = head;
        ListNode* two = head->next;
        ListNode* three = head->next->next;

        two->next = one;
        one->next = swapPairs(three);

        return two;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

注意几个细节：

1、虚拟头结点

2、fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）

3、记得删除节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* slow = dummyhead;
        ListNode* fast = dummyhead;
        while(n--&&fast!=nullptr){
            fast = fast->next;
        }
        fast = fast->next;
        while(fast!=nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode*temp = slow->next;
        slow->next = slow->next->next;
        delete temp;
        temp = nullptr;
        head = dummyhead->next;
        delete dummyhead;
        dummyhead = nullptr;
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

面试题 02.07. 链表相交

借助哈希（空间复杂度高）

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> set1;
        ListNode*temp = headA;
        while(temp != nullptr){
            set1.insert(temp);
            temp = temp->next;
        }
        temp = headB;
        while(temp != nullptr){
            if(set1.count(temp)){   //set::count()是C++ STL中的内置函数，
                        //返回元素在集合中出现的次数。由于set容器仅包含唯一元素，因此只能返回1或0。
                return temp;
            }
            temp = temp->next;
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

双指针（长度差值）

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int LenthA = 0;
        int LenthB = 0;
        while(curA != nullptr){
            curA = curA->next;
            LenthA++;
        }
        while(curB != nullptr){
            curB = curB->next;
            LenthB++;
        }
        curA = headA;
        curB = headB;
        if(LenthB>LenthA){
            swap(LenthA,LenthB);
            swap(curA,curB);
        }
        int gap = LenthA - LenthB;
        while(gap--){
            curA = curA->next;
        }
        while(curA!=nullptr){
            if(curA == curB){
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

142. 环形链表 II

思路：代码随想录 (programmercarl.com)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast!=nullptr&&fast->next!=nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                ListNode*index1 = fast;
                ListNode*index2 = head;
                while(index1 != index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21