手把手刷数据结构-1.手把手刷链表算法

1. 手把手刷链表算法

• 双指针秒杀7道链表题目
• • 合并两个有序链表
  • 合并 k 个有序链表
  • 单链表的倒数第 k 个节点
  • 单链表的中点
  • 判断链表是否包含环
  • 链表中环的入口节点
  • 两个链表是否相交
• 递归反转链表的一部分
• • 反转链表
  • 反转链表前N个节点
  • 反转链表II
• 如何K个一组反转链表
• 如何判断回文链表

双指针秒杀7道链表题目

链接: labuladong的算法小抄.

合并两个有序链表

力扣: 合并两个有序链表.

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(-1), *p = dummy;
        ListNode* p1 = list1, *p2 = list2;

        while (p1 != nullptr && p2 != nullptr) {
            // 比较 p1 和 p2 两个指针
            // 将值较小的节点接到 p 指针
            if (p1->val > p2->val) {
                p->next = p2;
                p2 = p2->next;
            } else {
                p->next = p1;
                p1 = p1->next;
            }
            p = p->next;
        }
        if (p1 != nullptr) {
            p->next = p1;
        } 
        if (p2 != nullptr) {
            p->next = p2;
        }
        return dummy->next;
    }
};

合并 k 个有序链表

力扣: 合并k个有序链表.

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 优先队列，最小堆 无论入队顺序如何，都是当前最小的元素优先出队
        priority_queue<int> q;
        // 将所有值直接放入优先队列中
        for (ListNode* &t : lists) {
            while (t) {
                q.push(t->val);
                t = t->next;
            }
        }
        ListNode *last = NULL;
        while (!q.empty()) {
            ListNode *p = new ListNode(q.top());
            q.pop();
            p->next = last;
            last = p;
        }
        return last;
    }
};

单链表的倒数第 k 个节点

力扣: 单链表的倒数第 k 个节点.

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) 
    {
        ListNode* fast = head;
        ListNode* later = head;

        while (fast && k > 0) {
            fast = fast->next;
            k--;
        }

        while (fast) {
            fast = fast->next;
            later = later->next;
        }
        return later;
    }
};

单链表的中点

链接: 单链表的中点.

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head, *slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

判断链表是否包含环

链接: 判断链表是否包含环.

class Solution {
public:
    bool hasCycle(ListNode *head) {
           // 快慢指针初始化指向 head
        ListNode* fast = head, *slow = head;
         // 快指针走到末尾时停止
        while (fast != nullptr && fast->next != nullptr) {
              // 慢指针走一步，快指针走两步
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，说明含有环
            if (fast == slow) {
                return true;
            }
        }
        // 不包含环
        return false;
    }
};

链表中环的入口节点

进阶：链接: 链表中环的入口节点.

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head, *slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) break;
        }

        if (fast == nullptr ||fast->next == nullptr) {
            return nullptr;
        }

        slow = head;
        while (fast != slow) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

两个链表是否相交

链接: 两个链表是否相交.

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
        ListNode* p1 = headA, *p2 = headB;
        while (p1 != p2) {
            // p1 走一步，如果走到 A 链表末尾，转到 B 链表
            if (p1 == nullptr) p1 = headB;
            else p1 = p1->next;
             // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if (p2 == nullptr) p2 = headA;
            else p2 = p2->next;
        }
        return p1;
    }
};

递归反转链表的一部分 反转链表

链接: 反转链表.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 链表为空，返回，如果链表只有一个节点的时候反转也是它自己，返回。
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

反转链表前N个节点

ListNode* successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode *head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head->next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode* last = reverseN(head->next, n - 1);

    head->next->next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head->next = successor;
    return last;
}

反转链表II

链接: 反转链表II.

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // base case
        if (left == 1) {
            return reverseN(head, right);
        }
        // 前进到反转的起点触发 base case
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }

    ListNode* successor = nullptr; // 后驱节点

    // 反转以 head 为起点的 n 个节点，返回新的头结点
    ListNode* reverseN(ListNode *head, int right) {
        if (right == 1) {
                // 记录第 n + 1 个节点
            successor = head->next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode* last = reverseN(head->next, right - 1);

        head->next->next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head->next = successor;
        return last;
    }
};

如何K个一组反转链表

链接: 如何K个一组反转链表.

class Solution {
public:

    /** 反转区间 [a, b) 的元素，注意是左闭右开 */
    ListNode* reverse(ListNode* a, ListNode* b) {
        ListNode* pre = nullptr, *cur = a, *next = a;
        while (cur != b) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr) return nullptr;
         // 区间 [a, b) 包含 k 个待反转元素
        ListNode* a, *b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // 不足 k 个，不需要反转，base case
            if (b == nullptr) return head;
            b = b->next;
        }
        // 反转前 k 个元素
        ListNode* newNode = reverse(a, b);
        a->next = reverseKGroup(b, k);
        return newNode;
    }
};

如何判断回文链表

链接: 如何判断回文链表.

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* fast = head, *slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        if (fast != nullptr) {
            slow = slow->next;
        }

        ListNode* left = head;
        ListNode* right = reverse(slow);

        while (right != nullptr) {
            if (left->val != right->val) {
                return false;
            }
            left = left->next;
            right = right->next;
        }
        return true;
    }

    ListNode* reverse(ListNode* head) {
        ListNode *pre = nullptr, *cur = head, *next = head;
        while (cur != nullptr) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};