代码随想录leetcode200题之链表

作者：小蓝xlanll | 2024-05-12 06:44:41

踩

1 介绍

本博客用来记录代码随想录leetcode200题中链表部分的题目。

2 训练

题目1：203移除链表元素

C++代码如下，

/**
 * 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) {
        ListNode* p = new ListNode(0, head);
        ListNode* res = p;
        while (p->next != nullptr) {
            if (p->next->val == val) p->next = p->next->next;
            else p = p->next;
        }

        return res->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        p = ListNode(0, head)
        res = p
        while p.next is not None:
            if p.next.val == val:
                p.next = p.next.next 
            else:
                p = p.next 
        return res.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题目2：707设计链表

C++代码如下，

// struct ListNode {
//     int val;
//     ListNode* next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode* nx) : val(x), next(nx) {}
// };

class MyLinkedList {
private:
    ListNode* head; //head无实际含义

public:


    MyLinkedList() {
        head = new ListNode(0);
    }
    
    int get(int index) {
        //时间复杂度O(N)
        int i = 0;
        ListNode* p = head->next;
        while (p != nullptr) {
            if (i == index) return p->val;
            p = p->next;
            i += 1;
        }
        return -1;
    }
    
    void addAtHead(int val) {
        //时间复杂度O(1)
        ListNode* p = new ListNode(val, head->next);
        head->next = p; 
    }
    
    void addAtTail(int val) {
        //时间复杂度O(N)
        ListNode* p = head;
        while (p->next != nullptr) p = p->next;
        ListNode* t = new ListNode(val);
        p->next = t;
    }
    
    void addAtIndex(int index, int val) {
        //时间复杂度O(N)
        ListNode* p = head; //p从头结点开始算
        int i = 0;
        while (p != nullptr && i < index) {
            p = p->next;
            i += 1;
        }

        if (p == nullptr) return;

        ListNode* t = new ListNode(val, p->next);
        p->next = t;
    }
    
    void deleteAtIndex(int index) {
        //时间复杂度为O(N)
        ListNode* p = head; //p从头结点开始算
        int i = 0;
        while (p != nullptr && i < index) {
            p = p->next;
            i += 1;
        }

        if (p == nullptr || p->next == nullptr) return;

        p->next = p->next->next;
    }
};

/**
 * 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
78
79
80
81
82
83
84

python3代码如下，

class MyLinkedList:

    def __init__(self):
        self.head = ListNode(0)


    def get(self, index: int) -> int:
        #时间复杂度为O(N)
        i = 0
        p = self.head.next 
        while p is not None:
            if i == index:
                return p.val 
            p = p.next 
            i += 1
        return -1

    def addAtHead(self, val: int) -> None:
        #时间复杂度为O(1)
        p = ListNode(val, self.head.next)
        self.head.next = p

    def addAtTail(self, val: int) -> None:
        #时间复杂度为O(N)
        p = self.head 
        while p.next is not None:
            p = p.next 
        t = ListNode(val)
        p.next = t 

    def addAtIndex(self, index: int, val: int) -> None:
        #时间复杂为O(N)
        p = self.head 
        i = 0
        while p is not None and i < index:
            p = p.next 
            i += 1
        
        if p is None:
            return 
        
        t = ListNode(val, p.next)
        p.next = t 

    def deleteAtIndex(self, index: int) -> None:
        #时间复杂度为O(N)
        p = self.head 
        i = 0
        while p is not None and i < index:
            p = p.next 
            i += 1
        
        if p is None or p.next is None:
            return 
        
        p.next = p.next.next 



# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# 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

题目3：206. 反转链表

C++代码如下，

/**
 * 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) {
        if (head == nullptr || head->next == nullptr) { //特判空集或一个结点的时候
            return head;
        }

        ListNode* a = head;
        ListNode* b = a->next;

        while (a != nullptr && b != nullptr) {
            ListNode* t = b->next;
            b->next = a;

            a = b;
            b = t;
        }
        
        head->next = nullptr;
        return a;
    }
};
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

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None: #特判空集和一个结点的情况
            return head 

        a = head 
        b = a.next 
        while a is not None and b is not None:
            t = b.next

            b.next = a 

            a = b
            b = t 
        
        head.next = None 
        return a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目4：24两两交换链表中的节点

C++代码如下，

/**
 * 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 == nullptr || head->next == nullptr) { //特判空集或者只有一个结点的情况
            return head;
        }

        ListNode* a = head;
        ListNode* b = a->next;

        ListNode* res = b;
        ListNode* aprev = nullptr;

        while (a != nullptr && b != nullptr) {
            ListNode* t = b->next;

            b->next = a;
            a->next = t;
            if (aprev != nullptr) aprev->next = b;

            aprev = a;
            a = t;
            if (a != nullptr) b = a->next;
            else break;
        }

        return res;
    }
};
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

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None: #特判空集或者一个结点的情况
            return head 
        
        a = head 
        b = a.next 
        aprev = None 

        res = b 

        while a is not None and b is not None:
            t = b.next 

            b.next = a 
            a.next = t 
            if aprev is not None:
                aprev.next = b
            
            aprev = a 
            a = t
            if a is not None:
                b = a.next 
            else:
                break
        
        return res 
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

题目5：19删除链表的倒数第 N 个结点

C++代码如下，

/**
 * 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 k) {
        //删除倒数第k个结点，快慢指针法

        ListNode* dummy = new ListNode(0, head);

        ListNode* a = dummy;
        ListNode* b = dummy;

        while (k--) { //b先走k步
            b = b->next;
        }

        while (b->next != nullptr) { //b走到最后一个结点
            a = a->next;
            b = b->next;
        }

        if (a->next != nullptr) a->next = a->next->next;
        else cout << "a->next is nullptr!" << endl;

        return dummy->next;
    }
};
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

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        a = dummy
        b = dummy 

        while k > 0:
            b = b.next
            k -= 1

        while b.next is not None:
            b = b.next 
            a = a.next 
        
        a.next = a.next.next 
        return dummy.next 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题目6：面试题 02.07. 链表相交

C++代码如下，

/**
 * 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) {
        if(headA == nullptr || headB == nullptr) { //特判都为空集，或者有一方为空集的情况
            return nullptr;
        }
        
        ListNode* a = headA;
        ListNode* b = headB;

        bool flaga = true;
        bool flagb = true;
        while (a != b) {
            a = a->next;
            b = b->next;

            if (a == nullptr) {
                if (flaga) {
                    a = headB;
                    flaga = false;
                } else {
                    break;
                }
            }

            if (b == nullptr) {
                if (flagb) {
                    b = headA;
                    flagb = false;
                } else {
                    break;
                }
            }
        }

        if (a == b) return a;
        else 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
36
37
38
39
40
41
42
43
44
45
46
47

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA is None or headB is None:
            return None 
        
        a = headA 
        b = headB 
        flaga = True
        flagb = True 
        while a != b:
            a = a.next 
            b = b.next 

            if a is None:
                if flaga:
                    a = headB 
                    flaga = False
                else:
                    break 
            
            if b is None:
                if flagb:
                    b = headA 
                    flagb = False 
                else:
                    break 
        
        if a == b:
            return a 
        else:
            return None

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

题目7：142. 环形链表 II

C++代码如下，

/**
 * 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* a = head;
        ListNode* b = head;

        while (b != nullptr && b->next != nullptr) {
            a = a->next;
            b = b->next->next;

            //起点到环入口的距离为x
            //快慢指针相遇点到环入口的距离为y
            //环的周长为c
            //有x % c = y恒成立
            if (a == b) { 
                ListNode* t = head;
                while (t != a) {
                    t = t->next;
                    a = a->next;
                }
                return a;
            }
        }
        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

python3代码如下，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        a = head 
        b = head 

        while b is not None and b.next is not None:
            a = a.next 
            b = b.next.next 

            if a == b:
                t = head 
                while t != a:
                    t = t.next 
                    a = a.next 
                return a 
        return None 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3 参考

代码随想录官网

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/558008

代码随想录leetcode200题之链表

目录

1 介绍

2 训练

3 参考