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

LeetCode Reverse Nodes in k-Group

程序员文章站 2022-03-01 12:39:56
...

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

  • Only constant extra memory is allowed.
  • You may not alter the values in the list's nodes, only nodes itself may be changed.

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

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

示例 :

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

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

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

说明 :

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

题解:给定一个单链表和一个k,将单链表中每k个节点进行反转,然后将新生成的构成一个新的链表。

这里,是用一个stack来保存每k个节点,当节点个数为k个时,进行反转,利用stack栈的先进后出的特点即可。

public static ListNode reverseKGroup(ListNode head,int k)
    {
        if(head == null || k <= 1)
            return head;
        Stack<ListNode> stack = new Stack<>();               //用了一个栈来保存
        ListNode dummy = new ListNode(-1);               //新建了一个头节点,用来指向head节点
        dummy.next = head;
        ListNode pre = dummy;                           //两个节点
        ListNode curr = head;
        int num = 0;
        while(curr != null)                               //当在前的那个指针一直往前走,并且每走一步,都需要使得节点个数加1,而且要看该节点个数值是否为k个
        {
            num += 1;
            if(num % k == 0)
            {
                stack.push(curr);                      //如果是节点个数没有满足k,那么将这些节点全都放入stack栈中
                curr = curr.next;
                while(!stack.isEmpty())                //如果节点个数的和刚好为k,那么将保存在stack栈中的所有节点全部都取出来,然后重新构建单链表
                {
                    pre.next = stack.pop();
                    pre = pre.next;
                }
                pre.next = curr;               //这是每次k个节点反转之后,都将最后的那个指针指向下一个节点,防止断链
            }
            else if(num % k != 0)
            {
                stack.push(curr);
                curr = curr.next;
            }
        }
        return dummy.next;
    }

注释写在代码中,可以供参考。此题一开始lz没啥思路,后来想到引入一个stack用来保存需要反转的节点,那么就豁然开朗,然后利用两个节点来进行反转。