递归实现链表k个一组反转

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

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

  • 使用递归,时间复杂度O(n),空间复杂度O(1)

  • 为了方便处理,创建一个在head前面的节点hair.

  • 每次向递归方法中传入该组的头节点,头节点的上一个节点,以及个数k,然后对头节点后面的k个节点指针进行反转,首先判断是否需要反转,如果个数小于k则不需要反转,获得这个组最后一个节点的下一个节点,作为下一次递归调用的头节点,链表反转简单,三个指针pre,current,next即可。
    java实现代码:

    public class Solution {
      /**
       * 
       * @param head ListNode类 
       * @param k int整型 
       * @return ListNode类
       */
      public ListNode reverseKGroup (ListNode head, int k) {
          // write code here
          ListNode hair = new ListNode(0);
          hair.next = head;
          reverse(hair,head,k);
          return hair.next;
      }
    
      //返回该组反转后的尾节点的下一个
      public void reverse(ListNode pre,ListNode head,int k){
          int i = 0;
          ListNode pHead = head;
          while(pHead!=null&&i<k-1){
              i++;
              pHead = pHead.next;
          }
          if(i<k-1||pHead==null){
              pre.next = head;
              return;
          }
          ListNode groupNext = pHead.next;
          pre.next = pHead;
          //反转head后面的
          ListNode current = head;
          ListNode next = null;
          ListNode preNode = null;
          while(current!=null&&current!=groupNext){
              next = current.next;
              if(preNode!=null){
                  current.next=preNode;
                  preNode = current;
                  current = next;
              }else{
                  preNode = head;
                  preNode.next = pHead;
                  current = next;
              }
          }
          reverse(head,current,k);
      }
    }
全部评论

相关推荐

06-28 22:48
已编辑
广东金融学院 Java
小浪_Coding:学院本+这俩项目不是buff叠满了嘛
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务