题解 | #NC50 链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

题目描述

将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。
要求空间复杂度 O(1)
例如:
给定的链表是 1 -> 2 -> 3 -> 4 -> 5
对于 k = 2, 你应该返回 2 -> 1 -> 4 -> 3 -> 5
对于 k = 3, 你应该返回 3 -> 2 -> 1 -> 4 -> 5

解题思路

使用头插法双指针
使用双层循环,外循环依次遍历链表,使用双指针判断需要翻转的链表区间;内循环使用头插法翻转链表。
双指针
定义指针slowfast,fastslow相差为k,中间的即为需要翻转的节点
头插法
每次要将k个节点进行翻转,需要翻转k - 1次,每次将节点插入该链表区间的头部,如下图所示(k = 4):

  1. 定义当前区间的头结点cur和下一节点temp
    图片说明
  2. 进行第一次翻转后结果应该为[-1,4,3,2,1,5],过程如下:

    可得到当前顺序:[-1,2,1,3,4,5],即把2插到了链表头部
  3. 重复上述操作
    图片说明
    可把3插入到前面,得到[-1,3,2,1,4,5]。重复k - 1次可以完成该区间段的翻转

    源码

    public class Solution {
     /**
      * 
      * @param head ListNode类 
      * @param k int整型 
      * @return ListNode类
      */
     public ListNode reverseKGroup (ListNode head, int k) {
         // write code here
         if(head == null || head.next == null || k == 1){
             return head;
         }
         ListNode ans = new ListNode(-1); //虚节点,返回结果
         ans.next = head;
         ListNode slow = ans;
         ListNode fast = ans;
         ListNode cur = null;
         ListNode temp = null;
         for(int i = 1;fast.next != null;i++){
             if(i % k != 0){
                 fast = fast.next;
             }else{ //长度到达k,需要翻转链表了
                 cur = slow.next;               
                 for(int j = 0;j < k - 1;j++){
                     temp = cur.next;
                     cur.next = temp.next;
                     temp.next = slow.next;
                     slow.next = temp;    
                 }
                 slow = cur;
                 fast = cur;
             }
         }
         return ans.next;
     }    
    }

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
2022-12-19 15:48
重庆工商大学_2024
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议