Leetcode.com/problems/re…

Discuss:www.cnblogs.com/grandyang/p…

Given a linked list, reverse the nodes of a linked list k at 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.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

Input: the head = [1, 2, 3, 4, 5], k = 2 Output:,1,4,3,5 [2]Copy the code

Example 2:

Input: the head = [1, 2, 3, 4, 5], k = 3 Output:,2,1,4,5 [3]Copy the code

Example 3:

Input: head = [1,2,3,4,5] Output: [1,2,3,4,5] Example 4:

Input: head = [1], k = 1 Output: [1]

Constraints:

The number of nodes in the list is in the range sz.

1 <= sz <= 5000

0 <= Node.val <= 1000

1 <= k <= sz

Follow-up: Can you solve the problem in O(1) extra memory space?

Solution a:

/** * Example: * var li = ListNode(5) * var v = li.`val` * Definition for singly-linked list. * class ListNode(var `val`: Int) { * var next: ListNode? = null * } */ class Solution { fun reverseKGroup(head: ListNode? , k: Int): ListNode? { if (head? .next == null || k == 1) { return head } val dummy = ListNode(-1) var pre: ListNode? = dummy var cur: ListNode? = head dummy.next = head var i = 1 while (cur ! = null) { if (i % k == 0) { pre = reverseOneGroup(pre, cur.next) cur = pre? .next } else { cur = cur.next } i = ++i } return dummy.next } private fun reverseOneGroup(pre: ListNode? , tail: ListNode?) : ListNode? { val last: ListNode? = pre? .next var cur: ListNode? = last? .next while (cur ! = tail) { last? .next = cur? .next cur? .next = pre? .next pre? .next = cur cur = last? .next } return last } }Copy the code

Method 2:

/** * Example: * var li = ListNode(5) * var v = li.`val` * Definition for singly-linked list. * class ListNode(var `val`: Int) { * var next: ListNode? = null * } */ class Solution { fun reverseKGroup(head: ListNode? , k: Int): ListNode? { val dummy = ListNode(-1) var pre: ListNode? = dummy var cur: ListNode? = pre dummy.next = head var num = 0 while (cur ! = null) { num++ cur = cur.next } while (num > k) { cur = pre? .next for (index in 1 until k) { val tempNode = cur? .next cur? .next = tempNode? .next tempNode? .next = pre? .next pre? .next = tempNode } pre = cur num -= k } return dummy.next } }Copy the code

Method 3:

Recursively.

/** * Example: * var li = ListNode(5) * var v = li.`val` * Definition for singly-linked list. * class ListNode(var `val`: Int) { * var next: ListNode? = null * } */ class Solution { fun reverseKGroup(head: ListNode? , k: Int): ListNode? { var cur: ListNode? = head for (index in 1.. k) { if (cur == null) { return head } else { cur = cur.next } } val newHead = reverse(head, cur) head? .next = reverseKGroup(cur, k) return newHead } private fun reverse(head: ListNode? , tail: ListNode?) : ListNode? { var pre: ListNode? = null var tempHead = head while (tempHead ! = tail) { val t = tempHead? .next tempHead? .next = pre pre = tempHead tempHead = t } return pre } }Copy the code