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