【c 】“反转链表”相关的题目-ag真人游戏

1.反转链表：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

（1）这道题是经典的题目了，用迭代的方式解决也是很容易的，代码量也不大。分享一个我个人做题的方式，我会先在题目开头写注释，理清我结题的思路，然后写代码就很容易了。

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     listnode *next;
 *     listnode(int x) : val(x), next(null) {}
 * };
 */
class solution {
public:
    listnode* reverselist(listnode* head) {
        //首先需要判断特殊情况
        //需要三个指针实现，先记录当前节点的下一个节点，然后把当前节点的后继节点变成前一个节点，然后把当前节点变成前一个节点，然后把下一个节点变成当前节点往后循环，最后要注意链表的头结点边到最后了
        //开始撸
        if(head == nullptr || head->next == nullptr)
            return head;
        listnode* ppre = nullptr;
        listnode* pcur = head;
        listnode* pnext = nullptr;
        while(pcur != nullptr)
        {
            pnext = pcur->next;
            pcur->next = ppre;
            ppre = pcur;
            pcur = pnext;
        }return ppre;
    }
};

（2）递归解法：简直是优雅

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     listnode *next;
 *     listnode(int x) : val(x), next(null) {}
 * };
 */
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;
    }
};

2.反转链表ii:

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

（1）递归，空间换时间，我佛了。

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     listnode *next;
 *     listnode(int x) : val(x), next(null) {}
 * };
 */
class solution {
public:
    listnode* reversebetween(listnode* head, int m, int n) {
        //按照题意，时间复杂度为o(n)
        //可以使用迭代和递归两种方式进行，时间复杂度都是o(n)，但是递归的空间复杂度为o(n)，而迭代为o(1)
        
        //递归解法
        if(m == 1)
            return reversen(head, n);
        head->next = reversebetween(head->next, m-1, n-1);
        return head;  
    }
    listnode* successor = nullptr;
    listnode* reversen(listnode* head, int n)
    {
        if(n==1)
        {
            successor = head->next;
            return head;
        }
        listnode* last = reversen(head->next, n-1);
        head->next->next = head;
        head->next = successor;
        return last;
    }

（2）迭代实现

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     listnode *next;
 *     listnode(int x) : val(x), next(null) {}
 * };
 */
class solution {
public:
    listnode* reversebetween(listnode* head, int m, int n) {
        //按照题意，时间复杂度为o(n)
        //可以使用迭代和递归两种方式进行，时间复杂度都是o(n)，但是递归的空间复杂度为o(n)，而迭代为o(1)
        
        //迭代解法
        listnode* pcur = head;
        listnode* ppre = nullptr;
        listnode* pnext = nullptr;
        listnode* pprem = nullptr;
        listnode* pm = nullptr;
        for(int i=0;i1;i  )
        {
            pprem = pcur;
            pcur = pcur->next;
        }
        pm = pcur;
        for(int j=m;j<=n;j  )
        {
            pnext = pcur->next;
            pcur->next = ppre;
            ppre = pcur;
            pcur = pnext;
        }
        if(m != 1)
        {
            pprem->next = ppre;
        }
        pm->next = pnext;
        return m==1? ppre : head;
    }
};

 3.k个一组反转链表

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

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 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) {
        //先反转以head开头的k个元素
        //将第k 1个元素作为head递归调用reversekgroup函数
        //将上述两个过程的结果连接起来
        //base case 如果最后的元素不足k个，就保持不变
        if(head == nullptr)
            return nullptr;
        listnode* a = head;
        listnode* b = head;
        for(int i=0;i)
        {
            if(b == nullptr)
                return head;
            b = b->next;
        }
        listnode* newhead = reverse(a,b);
        a->next = reversekgroup(b,k);
        return newhead;
    }
    listnode* reverse(listnode* a, listnode* b)
    {
        listnode* pcur = a;
        listnode* ppre = nullptr;
        listnode* pnext = nullptr;
        while(pcur != b)
        {
            pnext = pcur->next;
            pcur->next = ppre;
            ppre = pcur;
            pcur = pnext;
        }
        return ppre;
    }
};