Reverse Linked List

Reverse a singly linked list.

Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while(head != null) {
            ListNode nextNode = head.next;
            head.next = pre;
            pre = head;
            head = nextNode;
        }
        return pre;
    }
}


Reverse Nodes in k-Group 
1)剩下不满k个的也反转
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode pre = null;
        ListNode nextNode = null;
        if(head == null) return head;
        ListNode node = head;

        int i = 0;
        while(i < k && node != null) {
            nextNode = node.next;
            node.next = pre;
            pre = node;
            node = nextNode;
            i++;
        }
        if(node != null) {
            head.next = reverseKGroup(nextNode, k);
        }

        return pre;
    }
}

2）剩下不满k个的不反转
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode pre = null;
        ListNode nextNode = null;
        if(head == null) return head;
        ListNode node = head;

        //I need to add somthing to check whether the remaining length is 
        //less or greater than k or not, if greater, no change; if less, return head
        int count = 1;
        ListNode cur = head;
        while(count < k && cur.next != null) { //if cur != null, then when remaining 
                                               //is k-1, still count = k
            cur = cur.next;
            count++;
        }
        if(count != k) return head;
        //这一段是加进来的

        int i = 0;
        while(i < k && node != null) {
            nextNode = node.next;
            node.next = pre;
            pre = node;
            node = nextNode;
            i++;
        }
        if(node != null) {
            head.next = reverseKGroup(nextNode, k);
        }

        return pre;
    }
}


2) 剩下不满k个的不反转 不用recursion
//no recursion
class Solution{
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;

        int len = 0;
        ListNode l = head; //len is the length of this list
        while(l != null){
            len++;
            l = l.next;
        }

        int round = len / k;   //cut the list, so we have 'round' lists with size k 
        if(round == 0) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for(int i = 0; i < round; i++){
            //for each list with size k, reverse it
            ListNode start = pre.next;
            ListNode then = start.next;
            for(int j = 0; j < k-1; j++)
            {
                start.next = then.next;
                then.next = pre.next;
                pre.next = then;
                then = start.next;
            }
            pre = start;
        }
        return dummy.next;
    }
}