4

算法系列：链表反转问题

 1 year ago
source link: https://muyuuuu.github.io/2022/06/24/link/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

本文集中写链表的反转问题，因为其他的链表相交、链表数量等问题比较简单，即使没啥算法经验也能写个差不多，而链表反转也算一种经典的递归问题。这个文章的文字描述太乱了，有时间回来补图。

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。反转链表有两种实现方式，一种是迭代式实现，一种是通过递归实现。先来看通过迭代实现：迭代的反转需要使用三个指针，pre，cur 和 nxt，核心思想就是 cur 不断的向后移动过程中，让 cur 指向 pre。而这一过程分为四步：

  1. nxt = nxt->next，先让 nxt 向后移动，因为 cur 指向 pre 之后，需要通过 nxt 找到下一个节点
  2. cur->next = pre，实现指针的反转，让 cur 指向上一个指针
  3. pre = cur，为下一次反转做准备，pre 就是在反转中要被指向的节点
  4. cur = nxt，cur 指向下一个节点，为下一次反转做准备

通过以上四点，我们可以在推出一些细节：

  1. pre 的初始值应该是 null，因为任何一个链表的末尾节点应该是空节点，而第一次反转时 cur 指向了 pre，因此 pre 也就是链表的末尾，因此 pre 初始为空
  2. cur 的初始值就是 head 节点，nxt 的初始值也是 head 节点，因为这样才能让 nxt = nxt->next 和 cur->next = pre 有意义
  3. 如果 nxt 指向 null，说明此时链表反转完毕，而 cur 指向的就是 nxt，因此最后要返回 pre 指针
class ListNode {
public:
    int val;
    ListNode* next = nullptr;
    ListNode() = default;
    ListNode(int x) : val{x} {};
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      ListNode* pre = nullptr;
      ListNode* cur = head;
      ListNode* nxt = head;
      while (nxt != nullptr) {
        nxt = nxt->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
      }
      return pre;
    }
};

至于递归方法就简单了很多：

  1. 如果这个节点是原链表的尾部节点，那么直接将其返回，而且每一层递归函数的返回值都是它。而尾部节点的判断方式就是 head->next == null。因此先写出部分程序：如下的程序中，任何一个递归函数返回的都是链表的尾部节点。
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* last = reverseList(head->next);
        return last;
    }
};
  1. 在找到尾部节点后，将其余节点依次反转即可。而且一定是在找到尾部节点后反转，如果在找到尾部节点之前就反转，链表就无法向下递归。
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; // 自己的下一个节点是 nullptr
        return last;
    }
};

92. 反转链表 II

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

我决定以后用递归了，如果用迭代去写，涉及的变量和程序都比较繁琐。基于上面的递归反转：和反转全部链表不同，部分反转链表，需要在反转后，将链表的尾部指向原链表不反转部分的下一个元素。之前指向的是 nullptr，那么这里就需要指向原链表不反转部分的第一个元素。并返回反转链表后的第一个节点。

class Solution {
public:
    ListNode* p = nullptr;
    ListNode* reverse(ListNode* node, int right) {
        // right=1 的时候，下一个元素就是不需要反转的链表的第一个元素
        if (right == 1) {
            p = node->next;
            return node;
        }
        ListNode* last = reverse(node->next, right - 1);
        node->next->next = node;
        // 之前指向 nullptr，现在指向 p
        node->next = p;
        return last;
    }

// 返回的是链表的头部
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 反转前 k 个链表
        if (left == 1) {
            return reverse(head, right);
        }
        // 递归，head->next 移动一次，left 和 right 都递减
        // head->next 指向链表的第一个元素，无论反转或不反转，也是递归的精髓
        head->next = reverseBetween(head->next, left-1, right-1);
        return head;
    }
};

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

和上一题一样，反转后的链表末尾元素需要指向不需要反转的链表的第一个元素。第一题，反转链表的末尾元素指向 nullptr，所以需要和 nullptr 判断关系，这里同理，只是不是 nullptr 了。

/**
 * 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* p1, ListNode* p2) {
        // 指向谁，就和谁判断，第一题的 nullptr 也是如此
        if (p1 == p2 || p1->next == p2) {
            return p1;
        }
        ListNode* last = reverse(p1->next, p2);
        p1->next->next = p1;
        p1->next = p2;
        return last;
    }

// 返回的是反转链表的头
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr)
            return nullptr;
        ListNode* p1 = head;
        ListNode* p2 = head;
        // 如果不够反转，就不用反转
        for (int i = 0; i < k; i++) {
            if (p2 == nullptr)
                return head;
            p2 = p2->next;
        }
        // 第一次链表反转，的第一个元素一定是最后链表的头，因此要返回
        ListNode* last = reverse(p1, p2);
        // 头指针变成局部链表的尾指针，串起整个链表
        head->next = reverseKGroup(p2, k);
        return last;
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK