欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【LeetCode】Reverse Nodes in k-Group(k个一组翻转链表)

程序员文章站 2022-04-15 16:36:41
这是LeetCode里的第25道题。 题目要求: 给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。 示例 : 给定这个链表:1->2->3->4->5 当 k = 2 时,应 ......

这是leetcode里的第25道题。

题目要求:

给出一个链表,每 个节点一组进行翻转,并返回翻转后的链表。

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

示例 :

给定这个链表:1->2->3->4->5

当 = 2 时,应当返回: 2->1->4->3->5

当 = 3 时,应当返回: 3->2->1->4->5

说明 :

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

设计思路:

使用分治法(应该可以这样说吧),不是要k个一组吗?那就把k个节点当做一小块,然后对这一小块进行倒置。然后再连接,难就是难在连接上。如下图(灵魂画师上线了!):

【LeetCode】Reverse Nodes in k-Group(k个一组翻转链表)

如图所示,r节点就是连接处,而且此时r节点指向的是null,当一组交换完后,p节点指向的也是null,而且p节点是这一组的最后一个节点。我们要做的就是把上一组完成的尾巴r节点连接上这一组交换完后的tail节点上。这就是关键之处。当然不能忘了,当到了最后一组不满足等于k时,要记得直接返回。

解题代码:

/**
 * definition for singly-linked list.
 * struct listnode {
 *     int val;
 *     listnode *next;
 *     listnode(int x) : val(x), next(null) {}
 * };
 */
class solution {
public:
    listnode* reverse(listnode *head,listnode *tail){
        if(head==tail)return head;
        listnode *p=head,*r=tail;
        stack<listnode*>sl;
        while(p!=r){
            sl.push(p);
            p=p->next;
        }
        while(!sl.empty()){
            r->next=sl.top();
            sl.pop();
            r=r->next;
        }
        r->next=null;
        return p;
    }
    listnode* reversekgroup(listnode* head, int k) {
        listnode *phead,*ptail,*res=null,*p,*r=null;
        int i=1;
        phead=ptail=head;
        while(ptail!=null){
            if(i==k){
                p=ptail->next;
                if(res==null)res=reverse(phead,ptail);
                else r->next=reverse(phead,ptail);
                r=phead;
                phead=ptail=p;
                i=1;continue;
            }
            ptail=ptail->next;
            i++;
        }
        if(i!=1){
            if(r==null)return head;
            r->next=phead;
        }
        return res;
    }
};

最后结果:

【LeetCode】Reverse Nodes in k-Group(k个一组翻转链表)

个人总结:

这道题难度是有的,也可以同过递归来缩短代码的长度。也可以在倒置之前先统计出长度,计算出需要倒置的次数,再保存起来。最后连接。