博客

问题：

反转一个链表中的每K个节点，如果链表长度不能被K整除，则最后余数节点保持不变。

思路：

分组，对每个分组进行链表转置。关键设计转置函数，对组内元素迭代反转。

java代码：

ListNode reverseKGroup(ListNode head,int k){
        if(head==null||k<=1)
            return head;
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode pre=dummy,cross=head;
        int count=0;
        while(cross!=null){
            count++;
            if(count%k==0){
                pre=reverse(pre,cross.next);
                cross=pre.next;
            }
            else{
                cross=cross.next;
            }
        }
        return dummy.next;
    }
    ListNode reverse(ListNode pre,ListNode next){
        ListNode last=pre.next;
        ListNode cur=last.next;
        while(cur!=next){
            last.next=cur.next;
            cur.next=pre.next;
            pre.next=cur;
            cur=last.next;
        }
        return last;
    }

解法二：

public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null) return null;
        ListNode start=new ListNode(0);
        ListNode tmp,end=head;
        start.next=head;
        head=start;
        for(int i=1;i<k;i++){
            end=end.next;
            if(end==null){
                    return head.next;
                }
        }
        while(true){
            for(int i=1;i<k;i++){
                tmp=start.next;
                start.next=start.next.next;
                tmp.next=end.next;
                end.next=tmp;
            }
            end=start;
            for(int i=0;i<k;i++){
                start=start.next;
            }
            for(int i=0;i<2*k;i++){
                end=end.next;
                if(end==null){
                    return head.next;
                }
            }
        }
    }