lintcode--450. K组翻转链表

描述

给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。
链表元素个数不是k的倍数，最后剩余的不用翻转。

样例

给出链表 1->2->3->4->5

k = 2, 返回 2->1->4->3->5

k = 3, 返回 3->2->1->4->5

代码

整体思路是每隔k个节点，进行逆置，随后拼接。

/** * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */

public class Solution {
    /** * @param head: a ListNode * @param k: An integer * @return: a ListNode */
    public ListNode reverseKGroup(ListNode head, int k) {
        // write your code here
        if(head==null||head.next==null||k==1){
            return head;
        }
        int count=0;
        ListNode s=null;
        ListNode newHead=null,tail=null;
        for(ListNode node=head;node!=null;){
            if(count==0){
                s=node;
                node=node.next;
            }
            else if(count==k-1){
                ListNode temp2=node;
                node=node.next;
                temp2.next=null;
                count=-1;
                ListNode node3=reverse(s);
                if(newHead==null){
                    newHead=node3;
                }else{
                    tail.next=node3;
                }
                tail=s;
            }else{
                node=node.next;
            }
            count++;
        }
        if(tail!=s){
            tail.next=s;
        }
        return newHead;
    }
    private ListNode reverse(ListNode head){
        if(head==null){
            return null;
        }
        ListNode pre=null;
        while(head!=null){
            ListNode next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
}