【leetcode】链表反转题目总结

206. 反转链表

全部反转

递归法和迭代法

/**
 * 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;
        }
        // 1. 递归法
        // ListNode* last = reverseList(head->next);
        // head->next->next = head;
        // head->next = nullptr;
        // return last;

        // 2. 迭代法
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        head->next = nullptr;
        return pre;
    }
};

25. 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:
    // 反转区间[a,b)的元素，左闭右开
    ListNode* reverseAb(ListNode* a, ListNode* b) {
        ListNode* pre = nullptr;
        ListNode* cur = a;
        while (cur != b) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        // base case
        if (head == nullptr) {
            return nullptr;
        }

        ListNode* a = head;
        ListNode* b = head;
        for (int i = 0; i < k; ++i) {
            // 不足 k 个，不需要反转，base case
            if (b == nullptr) {
                return head;
            }
            b = b->next;
        }

        // 反转前 k 个元素
        ListNode* newHead = reverseAb(a, b);
        // 递归反转后续链表并连接起来
        a->next = reverseKGroup(b, k);

        return newHead;
    }
};

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

其实就是两个一组反转链表，利用上个题目的方式：

/**
 * 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:
 // 反转区间[a,b)的元素，左闭右开
    ListNode* reverseAb(ListNode* a, ListNode* b) {
        ListNode* pre = nullptr;
        ListNode* cur = a;
        while (cur != b) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        // base case
        if (head == nullptr) {
            return nullptr;
        }

        ListNode* a = head;
        ListNode* b = head;
        for (int i = 0; i < k; ++i) {
            // 不足 k 个，不需要反转，base case
            if (b == nullptr) {
                return head;
            }
            b = b->next;
        }

        // 反转前 k 个元素
        ListNode* newHead = reverseAb(a, b);
        // 递归反转后续链表并连接起来
        a->next = reverseKGroup(b, k);

        return newHead;
    }

    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        return reverseKGroup(head, 2);
    }
};

递归法

/**
 * 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* newHead = head->next;
        ListNode* nextPairs = newHead->next;
        newHead->next = head;
        head->next = swapPairs(nextPairs);
        return newHead;
    }
};

迭代法

/**
 * 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) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* node = dummy;
        while (node->next != nullptr && node->next->next != nullptr) {
            ListNode* node1 = node->next;
            ListNode* node2 = node->next->next;
            node->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            node = node1;
        }
        return dummy->next;
    }
};

92. 反转链表 II

/**
 * 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:
    // 反转区间[a,b)的元素，左闭右开
    ListNode* reverseAb(ListNode* a, ListNode* b) {
        ListNode* pre = nullptr;
        ListNode* cur = a;
        while (cur != b) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        // 寻找到反转区间
        ListNode* a = dummy;
        ListNode* b = dummy;
        for (int i = 0; i < right; i++) {
            if (i < left - 1) {
                a = a->next;
            }
            b = b->next;
        }

        ListNode* tailHead = b->next;
        // 反转区间
        ListNode* newHead = reverseAb(a->next, tailHead);

        // 区间前后链接
        a->next->next = tailHead;
        a->next = newHead;
        
        return dummy->next;
    }
};

234. 回文链表

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

    bool isPalindrome(ListNode* head) {
        if (head == nullptr) return true;

        ListNode* fast = head;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }

        if (fast != nullptr) {
            slow = slow->next;
        }

        ListNode* p1 = head;
        ListNode* p2 = reverse(slow);
        while (p2 != nullptr) {
            if (p1->val != p2->val) return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};