k个一组翻转链表

  

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

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

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

示例 :

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

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

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

说明 :

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

  解法1:

  

 public static ListNode reverseKGroup(ListNode head,int k){
        /*定义一个双向队列*/
        Deque<ListNode> deque=new ArrayDeque<>(k);
        /*定义一个哑节点*/
        ListNode dumb=new ListNode(0);
        /*定义哑节点的下一个节点是头节点*/
        dumb.next=head;
        /*定义一个引用指向哑节点*/
        ListNode h=dumb;
        while (true){
            int c=1;
            /*读取k个节点放入双向队列中*/
            while (head!=null&&c<=k){
                deque.add(head);
                head=head.next;
                c++;
            }
            /*当数量不足为k时，不需要反转，把剩余的头节点拼接到最后节点的next*/
            if(c<=k){
                dumb.next=deque.pollFirst();
                break;
            }
            /*把双向队列里的元素从尾部出队列*/
            while (!deque.isEmpty()){
                dumb.next=deque.pollLast();
                dumb=dumb.next;
            }
        }
        return h.next;
    }

View Code

  解法2:

public static ListNode reverseKGroup1(ListNode head,int k){
        /*定义一个哑节点*/
        ListNode dumb=new ListNode(0);
        /*定义哑节点的下一个节点是头节点*/
        dumb.next=head;
        /*定义一个区域头节点*/
        ListNode pre=dumb;
        /*定义一个区域尾节点*/
        ListNode tail=dumb;
        while (true){
            /*计数变量*/
            int count=0;
            /*当遍历了k个节点后break*/
            while (tail!=null&&count!=k){
                tail=tail.next;
                count++;
            }
            /*如果tail==null说明不满足k数量，不需要反转，直接break整个循环*/
            if(tail==null){
                break;
            }
            /*创建引用，指向下一个区域的节点位置*/
            ListNode temp=pre.next;
            /*当区域的头节点和尾节点汇合时break循环*/
            while (pre.next!=tail){
                /*需要反转的第一个节点*/
                ListNode curr=pre.next;
                /*需要反转的第一个节点的下一个节点向前移动一个节点*/
                pre.next=curr.next;
                /*需要反转的第一个节点插入到区域尾节点的next*/
                curr.next=tail.next;
                tail.next=curr;
            }
            /*指向下一个区域*/
            pre=temp;
            tail=temp;
        }
        return dumb.next;
    }

View Code