leetcode-hot-100-20230918

Last updated on 2023年9月21日 上午

160. 相交链表（C++使用双指针实现）

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
/**
 * 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) {
        //思路：首先先比较两个链表的长度
        int lengthA = 0;
        int lengthB = 0;

        ListNode *head = headA;

        while(head != NULL){
            lengthA ++;
            head = head -> next;
        }

        head = headB;

        while(head != NULL){
            lengthB ++;
            head = head -> next;
        }

        ListNode *pA = headA;
        ListNode *pB = headB;

        //不一样长度
        int lengthDiff = abs(lengthA - lengthB);

        if(lengthDiff > 0){
            //那么将指针移动到相同的位置
            if(lengthA > lengthB){
                for(int i = 0;i < lengthDiff;i++){
                    pA = pA -> next;
                }
            }else{
                for(int i = 0;i < lengthDiff;i++){
                    pB = pB -> next;
                }
            }
        }

        while(pA && pB){
            if(pA == pB){
                return pA;
            }
            pA = pA -> next;
            pB = pB -> next;
        }

        return NULL;
    }
};

206. 反转链表（C++使用tmpNode交换实现）

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
/**
 * 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) {
        ListNode *currNode = head;
        //保存结果结点
        ListNode *resultNode = NULL;
        //保存暂时结点
        ListNode *tmpNode = NULL;

        //循环
        while(currNode != NULL){
            //tmpNode记录当前结点的下一个next结点，防止丢失
            tmpNode = currNode->next;
            //然后，将currNode的next指向resultNode
            currNode->next = resultNode;
            //然后，更新resultNode为currNode
            resultNode = currNode;
            //然后，更新currNode为tmpNode
            currNode = tmpNode;
        }

        return resultNode;
    }
};

234. 回文链表（C++实现）

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
/**
 * 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:
    bool isPalindrome(ListNode* head) {
        //思路：使用保存结点指针的数组，然后前后判断即可
        vector<ListNode*> keep;

        while(head != NULL){
            keep.push_back(head);
            head = head -> next;
        }

        for(int i = 0;i < keep.size() / 2;i++){
            if(keep[i]->val == keep[keep.size() - i - 1]->val){
                continue;
            }else{
                return false;
            }
        }

        return true;
    }
};

141. 环形链表（C++实现，使用unordered_set保存已经遍历过的结点，然后每次判断set中是否存在当前结点，如果存在直接返回true）

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //思路：使用set集合保存结点，然后判断即可
        unordered_set<ListNode*> keep;

        while(head != NULL){
            if(keep.count(head)){
                return true;
            }
            keep.insert(head);
            head = head -> next;
        }

        return false;
    }
};

142. 环形链表 II（C++实现，使用unordered_set保存结点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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) {
        unordered_set<ListNode*> keep;

        while(head != NULL){
            if(keep.count(head)){
                return head;
            }
            keep.insert(head);
            head = head -> next;
        }

        return NULL;
    }
};

142. 环形链表 II（C++使用快慢指针实现，两次循环）

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
/**
 * 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) {
        //思路：使用快慢指针，当第一次快指针遇到满指针时
        //将slow结点重新置为head，然后当两个指针再次遇到的时候，返回当前结点，就是结果结点
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != NULL && fast->next != NULL){
            slow = slow -> next;
            fast = fast -> next -> next;

            if(slow == fast){
                ListNode* index2 = head;
                ListNode* index1 = fast;

                while(index1 != index2){
                    index1 = index1 -> next;
                    index2 = index2 -> next;
                }
                return index2;
            }
        }

        return NULL;
    }
};

21. 合并两个有序链表（C++实现）

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
/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newHead = new ListNode(0);
        ListNode* resultHead = newHead;

        while(list1 != NULL && list2 != NULL){
            if(list1->val <= list2->val){
                newHead->next = list1;
                newHead = newHead -> next;
                list1 = list1 -> next;
            }else{
                newHead->next = list2;
                newHead = newHead -> next;
                list2 = list2 -> next;
            }
        }

        //将list1剩下的结点添加到新的结果链表后
        while(list1 != NULL){
            newHead -> next = list1;
            newHead = newHead -> next;
            list1 = list1 -> next;
        }

        //将list2剩下的结点添加到新的结果链表后
        while(list2 != NULL){
            newHead -> next = list2;
            newHead = newHead -> next;
            list2 = list2 -> next;
        }

        return resultHead -> next;
    }
};

2. 两数相加（C++实现）

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
/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //思路：使用进位和当前位变量控制加法进行
        ListNode* h1 = l1;
        ListNode* h2 = l2;

        ListNode* newHead = new ListNode(0);
        ListNode* resultNode = newHead;

        int jin = 0;
        int curr = 0;

        while(h1 != NULL && h2 != NULL){
            //当前位置应当保留的数值
            curr = (h1->val + h2->val + jin) % 10;
            //得到进位的数值
            jin = (h1->val + h2->val + jin) / 10;
            ListNode* tmpNode = new ListNode(curr);
            newHead -> next = tmpNode;
            newHead = newHead -> next;

            h1 = h1 -> next;
            h2 = h2 -> next;
        }

        //如果head1不为NULL
        while(h1 != NULL){
            //当前位置应当保留的数值
            curr = (h1->val + jin) % 10;
            //得到进位的数值
            jin = (h1->val + jin) / 10;
            ListNode* tmpNode = new ListNode(curr);
            newHead -> next = tmpNode;
            newHead = newHead -> next;

            h1 = h1 -> next;
        }

        //如果head2不为NULL
        while(h2 != NULL){
            //当前位置应当保留的数值
            curr = (h2->val + jin) % 10;
            //得到进位的数值
            jin = (h2->val + jin) / 10;
            ListNode* tmpNode = new ListNode(curr);
            newHead -> next = tmpNode;
            newHead = newHead -> next;
            h2 = h2 -> next;
        }

        //判断最后jin数值是否为0，不为0，继续增加
        if(jin != 0){
            ListNode* jinNode = new ListNode(jin);
            newHead -> next = jinNode;
            newHead = newHead -> next;
        }

        return resultNode -> next;
        
    }
};

#leetcode hot 100 #Alibaba
leetcode-hot-100-20230918
https://thewangyang.github.io/2023/09/18/leetcode-hot-100-20230918/
Author
wyy
Posted on
2023年9月18日
Updated on
2023年9月21日
Licensed under