408算法题leetcode--第14天

92. 反转链表 II

• 92. 反转链表 II
• 思路：头插法
• 时间：O(n)；空间：O(1)

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        // 头插法
        if(head == nullptr) return nullptr;
        ListNode* dummy_head = new ListNode(-1, head);
        ListNode* p = dummy_head;
        for(int i = 0; i < left - 1; i++){
            p = p->next;
        }
        ListNode* cur = p->next;
        ListNode* next = nullptr;
        for(int i = 0; i < right - left; i++){
            next = cur->next;
            cur->next = next->next;
            next->next = p->next;
            p->next = next;
        }
        return dummy_head->next;
    }
};

21. 合并两个有序链表

• 21. 合并两个有序链表
• 时间：O(n+m)；空间：O(1)

/**
 * 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) {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;
        ListNode* p = list1, *q = list2;
        ListNode* dummy_head = new ListNode(-1);
        ListNode* t = dummy_head;
        while(q && p){
            if(q->val <= p->val){
                t->next = q;
                q = q->next;
            } else {
                t->next = p;
                p = p->next;
            }
            t = t->next;
        }
        t->next = q == nullptr ? p : q;
        return dummy_head->next;
    }
};

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

• 24. 两两交换链表中的节点
• 思路：类似之前的头插法
• 时间：O(n)；空间：O(1)

/**
 * 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) return head;
        ListNode* dummy_head = new ListNode(-1, head);
        ListNode* pre = dummy_head, *cur = dummy_head->next;
        ListNode* next = nullptr;
        while(cur && cur->next){
            next = cur->next;
            // 头插法
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
            // 向后移动
            pre = cur;
            cur = cur->next;
        }
        return dummy_head->next;
    }
};

876. 链表的中间结点

• 876. 链表的中间结点
• 思路：快慢指针
• 时间：O(n)；空间：O(1)

/**
 * 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* middleNode(ListNode* head) {
        // 快慢指针：快指针走2步，慢指针走1步
        ListNode* fast = head, *slow = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};