LEETCODE 25. Reverse Nodes in k-Group 解题思路分析

题目大意:

K 个一组翻转链表

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

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

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

示例:

给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5

说明:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=25

解题思路分析:

本题我们可以借助一个Stack来解题。我们从链表头部开始,向Stack中插入k个节点,然后在按顺序pop出来实际上就是将这k个节点翻转了一遍。另外如果stack中元素个数不到k个,顺序保持不变即可。

实现代码:

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next=head;
    ListNode lastEnd=dummy;
    Stack<ListNode> stack=new Stack<>();
    while(head!=null){
        ListNode first=head;
        while(stack.size()<k&&head!=null){
            stack.push(head);
            head=head.next;
        }
        if(stack.size()<k) {
            lastEnd.next=first;
            break;
        }
        lastEnd.next=help(stack);
        lastEnd=first;
    }
    return dummy.next;
}

ListNode help(Stack<ListNode> stack){
    if(stack.size()==0) return null;
    ListNode node = stack.pop();
    node.next=help(stack);
    return node;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 21.90% of Java online submissions for Reverse Nodes in k-Group.

Memory Usage: 40.3 MB, less than 5.17% of Java online submissions for Reverse Nodes in k-Group.


Kotlin版本实现代码:

fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    val dummy = ListNode(0);
    dummy.next=head;
    var lastEnd = dummy;
    var stack=Stack<ListNode>();
    var hd = head;
    outloop@ while(hd!=null){
        var first = hd;
        while(stack.size<k&&hd!=null){
            stack.push(hd);
            hd=hd.next;
        }
        if(stack.size<k) {
            lastEnd.next=first;
            break@outloop;
        }
        lastEnd.next=help(stack);
        while(lastEnd.next!=null){
            lastEnd=lastEnd.next;
        }
    }
    return dummy.next;
}

fun help(stack: Stack<ListNode>) : ListNode?{
    if(stack.size==0) return null;
    var node = stack.pop();
    node.next=help(stack);
    return node;
}

本题解法执行时间为180ms。

Runtime: 180 ms, faster than 70.00% of Kotlin online submissions for Reverse Nodes in k-Group.

Memory Usage: 34.6 MB, less than 100.00% of Kotlin online submissions for Reverse Nodes in k-Group.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-25-reverse-nodes-in-k-group-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。