25. Reverse Nodes in k-Group

25. Reverse Nodes in k-Group

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 nodes, only nodes itself may be changed.

Only constant memory is allowed.

For 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

思路：

先让头结点的next域指向结点2，再让结点1的next域指向结点3，最后将结点2的next域指向结点1，就完成了第一次交换，顺序就变成了Header-结点2-结点1-结点3-结点4-NULL，然后进行相同的交换将结点3移动到结点2的前面，然后再将结点4移动到结点3的前面就完成了反转。

/** * 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 root = new ListNode(-1); root.next = head; ListNode res = root; ListNode temp = head; int i = 0; while(temp != null){ i++; temp = temp.next; } while(i >= k){ for(int j = 0 ; j < k-1; j++){ ListNode node = root.next; root.next = head.next; head.next = root.next.next; root.next.next = node; } root = head; head = head.next; i-=k; } return res.next; }}

/** * 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) { // 1->2, 3->4->5 ListNode newHead = null, prev = null, start = head, prevTail = null; int counter = 0; for(ListNode temp = head; temp != null; temp = temp.next) { if(counter == k) { prev.next = null; ListNode revHead = reverseNodes(start); if(newHead == null) newHead = revHead; if(prevTail != null) prevTail.next = revHead; prevTail = start; start.next = temp; start = temp; counter = 1; } else { counter++; } prev = temp; } if(counter == k) { ListNode revHead = reverseNodes(start); if(newHead == null) newHead = revHead; if(prevTail != null) prevTail.next = revHead; } return newHead; } //returns the new head of the reversed LL ListNode reverseNodes(ListNode root) { ListNode prev = null, current = root; while(current != null) { ListNode next = current.next; current.next = prev; prev = current; current = next; } return prev; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。