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.
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.
题意：
给定一个链表，每k个节点一组，做一次反转。
Solution1：we can still simplify this question into how to reverse a linked list, the only difference is we need to set "dummy" and "null" like the left and right boundary by ourselves.
(1) set a pointer pre as a " dummy " ahead
(2) set a pointer last as a " null " boundary
(3) iteratively move cur into the front(pre.next)
(4) cur = next
(5)iteratively move cur into the front(pre.next) until cur meet the "null" boundary
code:
1 /* 2 Time: O(n) 3 Space: O(1) 4 */ 5 class Solution { 6 public ListNode reverseKGroup(ListNode head, int k) { 7 if (head == null) return null; 8 ListNode dummy = new ListNode(-1); 9 ListNode pre = dummy; 10 dummy.next = head; 11 // to reverse each k-Group, considering pre as a "dummy" ahead 12 while (pre != null) { 13 pre = reverse(pre, k); 14 } 15 return dummy.next; 16 } 17 18 public ListNode reverse(ListNode pre, int k) { 19 // to reverse each k-Group, considering last as a "null" boundary 20 ListNode last = pre; 21 for (int i = 0; i < k + 1; i++) { 22 last = last.next; 23 if (i != k && last == null) return null; 24 } 25 26 // reverse 27 ListNode tail = pre.next; 28 ListNode cur = pre.next.next; 29 // remove cur to front, then update cur 30 while (cur != last) { 31 ListNode next = cur.next; 32 cur.next = pre.next; 33 pre.next = cur; 34 tail.next = next; 35 cur = next; 36 } 37 return tail; 38 } 39 }
转载于:https://www.cnblogs.com/liuliu5151/p/10674647.html
