This is the 16th day of my participation in the August More Text Challenge. For details, see:August is more challenging
Today is August 16, this month has 31 days, finished today, this month’s activities have completed half.
In the past two weeks, except for work, everything else went well. I wrote an article every day, exercised 5 days a week for at least 30 minutes each time, and my several flags were not failed. Recently, I watched some short videos of used cars, and found a particularly obvious phenomenon: the more high-end used cars are sold, the more mundane, the more polite the characters are, and the more trust in the transaction. At the lower end of the used car trade, the story becomes more convoluted, full of pits, full of intrigues, and too dramatic to believe that this is really happening. If you think about it, maybe it’s two different groups of people. People at the bottom are more likely to enjoy these conflicts, and they live in a world where things like these pits are more common, which fits their worldview; People at the top are more peaceful, more looking at cars, know the people who are trading, and with a sense of trust, trading is a more natural result. Therefore, when you want to complain, you may want to reflect on whether your energy is not enough, the level is not high enough, so the surrounding environment is more hostile, to inward attribution to improve themselves, is a hard way out of the harsh environment, but also the most recent shortcut.
Thought so much, continue to brush to improve the technology, today do Leetcode problem 25.
The title
I give you a list, and I flip it every k nodes, and I ask you to return the list. K is a positive integer whose value is less than or equal to the length of the list. If the total number of nodes is not an integer multiple of K, leave the last remaining nodes in their original order.
Advanced: Can you design an algorithm that only uses constant extra space to solve this problem? You can’t just change the values inside a node, but actually switch nodes.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Example 2:
Input: head = [1,2,3,4,5], k = 3
Example 3: Input: head = [1,2,3,4,5], k = 1 Output: [1,2,3,4,5]
Example 4: Input: head = [1], k = 1 Output: [1]
Train of thought
Divided into small lists of length K, the last group may be less than K. For this k small list, do a complete reversal, and then end up, and then less than k small list, do not reverse, directly in the end of the append. See the figure below
The small list itself completely inverted method:
- Define a pre node to be null and a current node to point to the head node
- Record the next node of current as next
- Current’s next points to pre
- Current as pre, next as current
- Loop 2-4 until the list ends
Java version code
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(); ListNode tail = dummy; ListNode index = head; while (index ! = null) {if (hasKListNode(index, k)) {ListNode subHead = index; For (int I = 0; i < k; i++) { index = index.next; } next = reverseKListNode(subHead, k); next = reverseKListNode(subHead, k); // The head node of the original small list is the tail node of the latest result list, which is the latest tail tail = subHead; } else {// there are less than k nodes left // Next of the current tail node points to the remaining head node tail.next = index; break; } } return dummy.next; } /** * Whether to include k nodes ** @param index * @param k * @return */ private static Boolean hasKListNode(ListNode index, int k) { while (k-- > 0) { if (index == null) { return false; } index = index.next; } return true; } /** * @param head ** @param len * @return */ private static ListNode reverseKListNode int len) { ListNode pre = null; ListNode current = head; while (len-- > 0) { ListNode next = current.next; current.next = pre; pre = current; current = next; } // If pre is the new list header return pre; }}Copy the code