【反转链表专题】【LeetCode206.反转链表】&【LeetCode25.K个一组翻转链表】&【LeetCode234.回文链表】

题目链接

• 反转链表：206. 反转链表 - 力扣（LeetCode）
• K个一组翻转链表：25. K 个一组翻转链表 - 力扣（LeetCode）
• 回文链表：234. 回文链表 - 力扣（LeetCode）

实现思路

代码实现

• 反转链表：

/**
 * 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* pre = nullptr;
        ListNode* cur = head;
        while(cur) {
            ListNode* next = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

• K个一组翻转链表

/**
 * 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:
    vector<ListNode*> reverse(ListNode* head, ListNode* next) {
        ListNode* pre = next;
        ListNode* cur = head;
        while (cur != next) {
            ListNode* nextNode = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nextNode;
        }
        return {pre, head}; // pre是反转之后的头节点,head是反转之后的尾节点
    }
 
    ListNode* reverseKGroup(ListNode* head, int k) {
        int cnt = 0;
        ListNode* cur = head;
        ListNode* preHead = new ListNode(-1);
        preHead -> next = head;
        ListNode* pre = preHead;
        while (cur) {
            cnt++;
            if (cnt % k == 0) {
                cnt = 0;
                vector<ListNode*> res = reverse(pre->next, cur->next);
                pre->next = res[0];
                cur = res[1];
                pre = cur;
            }
            cur = cur -> next;
        }
        return preHead -> next;
    }
};

• 回文链表

/**
 * 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* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* next = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        if (head -> next == nullptr) return true;
        ListNode* preHead = new ListNode();
        preHead -> next = head;
        ListNode* slow = preHead;
        ListNode* fast = preHead;
        while (fast != nullptr && fast -> next != nullptr) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        // 反转slow->next到tail的部分
        ListNode* head1 = slow -> next;
        head1 = reverse(head1);
        ListNode* cur = head;
        ListNode* cur1 = head1;

        while (cur1) {
            if (cur -> val != cur1 -> val) {
                return false;
            }
            cur = cur -> next;
            cur1 = cur1 -> next;
        }
        return true;
    }
};