leetcode-25-reverse-nodes-in-k-group

Description

Given a linked list, reverse the nodes of a linked list kat a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list’s nodes, only nodes itself may be changed.

思路0

題意可知，要就是做length/k次單鏈表反轉

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
   public ListNode reverseKGroup(ListNode head, int k) {
      ListNode dummy = new ListNode(0);
      dummy.next = head;

      ListNode pre = dummy;
      ListNode end = dummy;

      while (end.next != null) {
          for (int i = 0; i < k && end != null; i++) end = end.next;
          if (end == null) break;
          ListNode start = pre.next;
          ListNode next = end.next;
          end.next = null;
          pre.next = reverse(start);
          start.next = next;
          pre = start;

          end = pre;
      }
      return dummy.next;
  }

  private ListNode reverse(ListNode head) {
      ListNode pre = null;
      ListNode curr = head;
      while (curr != null) {
          ListNode next = curr.next;
          curr.next = pre;
          pre = curr;
          curr = next;
      }
      return pre;
  }


}