leetcode-链表篇3

leetcode-61

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

leetcode.com%2Fuploads%2F2020%2F11%2F13%2Frotate1.jpg&pos_id=cLotG7Yi" width="534" />
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

思路：看图片可以发现，这个题目本质上，是把链表分成两部分，交换前后两部分的顺序

所以重点在于找到分裂点，以及拼接

/**
 * 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* rotateRight(ListNode* head, int k) {
        if(!head || !head->next || k == 0) {
            return head;
        }
        auto tmp = head;
        int count = 0;
        auto tail = head;
        while(tmp) {
            tail = tmp;
            tmp = tmp->next;
            ++count;
        }
        tmp = head;
        k %= count;
        if(k == 0) {
            return head;
        }
        k = count - k;
        while(--k && tmp) {
            tmp = tmp->next;
        }
        auto new_head = tmp->next;
        tmp->next = nullptr;
        tail->next = head;
        return new_head;
    }   
};

leetcode-206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

leetcode.com%2Fuploads%2F2021%2F02%2F19%2Frev1ex1.jpg&pos_id=cxsJkjIs" width="534" />
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：

leetcode.com%2Fuploads%2F2021%2F02%2F19%2Frev1ex2.jpg&pos_id=hN0iV2D1" width="534" />
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思路：递归法比较简单，还是我们的老模板

void circle(ListNode *head) {

    if(...) {
        return 
    }        //边界条件

    auto res = circle(head->next);
    
    //other code
    //return
}

迭代法也是一器破万法。

关于链表反转的题目，都分成两部分，pre和curr

pre就是已经处理好的部分的尾节点， curr就是你要处理的部分的头节点

所以伪代码如下

//关于翻转链表相关的题目
while(xxx) {
    process(curr);      //实现翻转的逻辑
    pre = curr;         //当前部分已经处过，所以pre变成curr
    curr = curr->next;  //curr->next还没处理过，所以curr指向自己的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* reverseList(ListNode* head) {
        if(!head || !head->next) {
            return head;
        }
        // auto next = reverseList(head->next);
        // auto tmp = head->next;
        // head->next = nullptr;
        // tmp->next = head;
        // return next;
        auto pre = head;
        pre = nullptr;
        while(head) {
            auto next = head->next;
            head->next = nullptr;
            head->next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
};

leetcode-92

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

leetcode.com%2Fuploads%2F2021%2F02%2F19%2Frev2ex2.jpg&pos_id=OOBppl2a" width="534" />
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

思路，和上题一样，不过是对翻转的区间有限制了。

加上前缀节点pre，找到要翻转的区间的头尾节点，将之翻转后。拼接回原来的链表

/**
 * 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 || !head->next) {
            return head;
        }
        auto tmp = new ListNode(-1);
        tmp->next = head;
        auto pre = tmp;
        int count = left;
        while(--count) {
            tmp = tmp->next;
        }
        auto curr = tmp->next;
        for(int i=0; i<right-left; i++) {
            auto tail = curr->next->next;
            auto next = curr->next;
            curr->next = tail;

            auto new_tail = tmp->next;
            tmp->next = next;
            next->next = new_tail;
        }
        return pre->next;
    }
};

leetcode-24

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

leetcode.com%2Fuploads%2F2020%2F10%2F03%2Fswap_ex1.jpg&pos_id=gllGTNzY" width="534" />
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

思路：还记得我们一器破万法的迭代法模板吗，直接套用就可以

/**
 * 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 || !head->next) {
            return head;
        }
        auto pre = new ListNode(-1);
        pre->next = head;
        auto curr = head;
        auto tmp = pre;
        while(curr && curr->next) {
            auto tail = curr->next->next;
            auto next = curr->next;
            curr->next = tail;

            auto new_tail = tmp->next;
            next->next = new_tail;
            tmp->next = next;

            tmp = curr;
            curr = curr->next;
        }
        return pre->next;
    }
};

leetcode-25

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2：

leetcode.com%2Fuploads%2F2020%2F10%2F03%2Freverse_ex2.jpg&pos_id=KgOPaJF4" width="534" />
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

思路：做了以上几道题目，总结了自己的一器破万法模板之后，发现这个题竟然这么简单

以前被自己视为面试杀手的接雨水，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:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto tmp = head;
        int count=0;
        while(tmp) {
            ++count;
            tmp = tmp->next;
        }
        if(!head || !head->next || k>count || k<=1) {
            return head;
        }
        auto pre = new ListNode(-1);
        pre->next = head;
        tmp = pre;
        auto curr = head;    
        for(int i=0; i<count/k; i++) {
            for(int j=1; j<k; j++) {
                auto tail = curr->next->next;
                auto next = curr->next;
                curr->next = tail;

                auto new_tail = tmp->next;
                next->next = new_tail;
                tmp->next = next;
            }
            tmp = curr;
            curr = curr->next;
        }
        return pre->next;
    }
};