Given a singly linked list and an integer K, reverses the nodes of the
list K at a time and returns modified linked list.
NOTE : The length of the list is divisible by K
Example :
Given linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 and K=2,
You should return 2 -> 1 -> 4 -> 3 -> 6 -> 5
Try to solve the problem using constant extra space.
Method:
Reverse k elements at a time
Solution:
Time: O(n) Space: O(1)
/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */ public class Solution { // s e // 1->2->3->4 // 1<-2<-3->4 // 3->2->1->4
// 3->2->1->4->5->6 // public ListNode reverse(ListNode start, ListNode end, ListNode previous) { ListNode n = end.next; ListNode prev = null; ListNode p = start; while (p != n) { ListNode next = p.next; p.next = prev; prev = p; p = next; } start.next = n; previous.next = prev; return prev; }
public ListNode reverseList(ListNode A, int B) { ListNode start = A; ListNode end = A; ListNode dummy = new ListNode(0); ListNode prev = dummy; while (end != null) { for (int i = 1; i < B; i ++) { end = end.next; } ListNode next = end.next; ListNode newHead = reverse(start, end, prev); prev = start; start = next; end = next; } return dummy.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 { // (0) 1 2 3 4 5 // d c n e // (0) 3 2 1 4 5 // r private ListNode reverse(ListNode dummy, ListNode end) { ListNode curr = dummy.next; ListNode ret = curr; ListNode prev = end; while (curr != end) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } dummy.next = prev; return ret; }
public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode curr = dummy.next; ListNode prev = dummy; int count = 0; while (curr != null) { count ++; if (count % k == 0) { prev = reverse(prev, curr.next); curr = prev.next; } else { curr = curr.next; } } return dummy.next; } }